1456 

  1457 \begin{tabular}{lll}

  1458   TAs: & Anton Luca-Dorin & (took the module last year)\\

  1459        & Chengsong Tan    & (PhD student working on derivatives)  

  1460 \end{tabular}  

  1463 

  1464 \begin{frame}[c]

  1465 \begin{mybox3}{Coursework}

  1466   Do we need to provide instructions on running the coursework files

  1467   if we're using languages other than Scala? Thanks

  1468 \end{mybox3}\pause

  1469 

  1470 \begin{mybox2}{Zip-File for Coursework}

  1471   Please, please submit a zipfile that generates a subdirectory

  1472   \begin{center}

  1473   \texttt{NameFamilyName}  

  1474   \end{center}  

  1475 \end{mybox2}

  1476 \end{frame}

  1477 

  1478 

  1479 \begin{frame}[c]

  1480 \begin{mybox3}{Coursework}

  1481   What is the purpose of the workshop session on the timetable?

  1482   

  1483   Slightly confused about how to undertake cw1 and what exactly we

  1484   should be implementing. This is more for clarification of the cw1

  1485   structure, including the implementation and questions present in

  1486   cw1.

  1487 \end{mybox3}

  1488 \end{frame}

  1489 

  1490 \begin{frame}[c]

  1491 \begin{mybox3}{What is the trick?}\small

  1492   What was the trick to improve the evil regular expressions matcher

  1493   to have such good results compared to other programming languages?

  1494   Is it working better on casual regular expressions (the ones that

  1495   Python and Java handle pretty well), too? Or was it just optimised

  1496   for these evil ones?

  1497 \end{mybox3}

  1498 

  1499 \begin{mybox3}{}\small

  1500   It was shown in the lectures that the pattern matching algorithms

  1501   currently implemented in popular programming languages (Python, JS,

  1502   Java, etc) are far slower than the algorithm we are going to be

  1503   implementing in this module. My question is why do these programming

  1504   languages not implement the algorithm that we are going to implement

  1505   in this module?

  1506 \end{mybox3}

  1507 \end{frame}

  1508 

  1509 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1510 \begin{frame}[c]

  1511   \frametitle{Thanks to Martin Mikusovic}

  1512 

  1513 \bigskip    

  1514 \begin{center}

  1515 \begin{tikzpicture}

  1516   \begin{axis}[

  1517     xlabel={$n$},

  1518     x label style={at={(1.05,0.0)}},

  1519     ylabel={time in secs},

  1520     enlargelimits=false,

  1521     xtick={0,5,...,30},

  1522     xmax=33,

  1523     ymax=35,

  1524     ytick={0,10,...,30},

  1525     scaled ticks=false,

  1526     axis lines=left,

  1527     width=9cm,

  1528     height=5.5cm, 

  1529     legend entries={Java 8, Python, JavaScript, Swift},  

  1530     legend pos=north west,

  1531     legend cell align=left]

  1532 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};

  1533 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};

  1534 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data};

  1535 \addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};

  1536 \end{axis}

  1537 \end{tikzpicture}

  1538 \end{center}

  1539 

  1540 Regex: \bl{$(a^*)^* \cdot b$}

  1541 

  1542 Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}

  1543 

  1544 \end{frame}

  1545 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1546 

  1547 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1548 \begin{frame}[c]

  1549 \frametitle{Same Example in Java 9+}

  1550 

  1551 \begin{center}

  1552 \begin{tikzpicture}

  1553   \begin{axis}[

  1554     xlabel={$n$},

  1555     x label style={at={(1.09,-0.15)}},

  1556     ylabel={time in secs},

  1557     scaled x ticks=false,

  1558     enlargelimits=false,

  1559     xtick distance=10000,

  1560     xmax=44000, 

  1561     ytick={0,10,...,30}, 

  1562     ymax=35, 

  1563     axis lines=left,

  1564     width=9cm,

  1565     height=5cm, 

  1566     legend entries={Java \liningnums{9}+},

  1567     legend pos=north west,

  1568     legend cell align=left]

  1569 \addplot[blue,mark=square*,mark options={fill=white}] table {re-java9.data};

  1570 \end{axis}

  1571 \end{tikzpicture}

  1572 \end{center}

  1573 

  1574 Regex: \bl{$(a^*)^* \cdot b$}

  1575 

  1576 Strings of the form \bl{$\underbrace{\,a\ldots a\,}_{n}$}

  1577 

  1578 \end{frame}

  1579 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1580 

  1581 \begin{frame}[c]

  1582 \begin{mybox3}{}

  1583   Are there any (common) languages that have a built-in regex

  1584   implementation matching the set of functions of a formal 'simple'

  1585   regular expression, as opposed to an 'extended' regular expression

  1586   implemented in most regex-supporting languages?

  1587 \end{mybox3}

  1588 \end{frame}

  1589 

  1590 \begin{frame}[c]

  1591 \begin{mybox3}{Passing Mark}

  1592   I believe the assessment is 70\% coursework (broken into 10\% weekly

  1593   stuff, 15\% mid term exam and 45\% CW in any programming language)

  1594   and 30\% January exam. However, I would like to know if we just need

  1595   40\% overall to pass the module or pass the each component

  1596   individually?

  1597 \end{mybox3}

  1598 

  1599 \hfill$\Rightarrow$ 40\% overall

  1600 \end{frame}

  1601 

  1602 \begin{frame}[c]

  1603 \begin{mybox3}{Regexes}

  1604   Can we determine all the possible regular expressions matching a

  1605   certain string? If we take into account all the possible ways to

  1606   combine the operations: \bl{$\ZERO$}, \bl{$\ONE$},

  1607   \bl{$r_1 + r_2$}, \bl{$r_1 \cdot r_2$}, \bl{$r^*$}?

  1608 \end{mybox3}

  1609 \end{frame}

  1610 

  1611 \begin{frame}[c]

  1612 \begin{mybox3}{\bl{$L$} + Equivalence}

  1613   When we explain why two regular expressions are not equivalent, what

  1614   method is better for us, using mathematics formulas or making an

  1615   example? 

  1616 \end{mybox3}

  1617 \begin{mybox3}{}

  1618   Meaning of Regex and Operations

  1619 \end{mybox3}

  1620 \end{frame}

  1621 

  1622 \begin{frame}[c]

  1623 \begin{mybox3}{\bl{$L$}}

  1624   Can the function L be applied to anything other than regular

  1625   expressions? For example would L(L(c)) return anything?

  1626 \end{mybox3}

  1627 

  1628 \hfill $\Rightarrow$ No

  1629 \end{frame} 

  1630 

  1631 \begin{frame}[c]

  1632 \begin{mybox3}{\bl{$(a?)\{n\} \cdot a\{n\}$}}

  1633   In the evil regexes section, is there any reason why in the regex

  1634   \texttt{[a?]\{n\}[a]\{n\}} the square brackets are used? It is defined as a

  1635   single character from the square brackets, however there is just one

  1636   character, so it seems like it is not necessary. Maybe it is just

  1637   necessary for the first part, because ? is a token instead of a

  1638   character and we need to refer to a? as a ``unit''? Could regular

  1639   brackets be used instead? Is there any difference apart from the

  1640   fact that it would create a group? Also, are the regexes

  1641   \texttt{[a?]\{n\}} and

  1642   \texttt{a\{0,3\}} equivalent?

  1643 \end{mybox3}

  1644 \end{frame} 

  1645 

  1646 \begin{frame}[c]

  1647 \begin{mybox3}{Python + Parser Combinators (CW3)}\small

  1648   Hi Christian,

  1649 

  1650   I don’t see a problem: you certainly have higher order functions and

  1651   it is easy to implement algebraic data types using classes. As far

  1652   as I can see that’s all you need. You don’t get the static types but

  1653   that should be obvious. Basically if you can do it in LISP you can

  1654   do it in Python. The only problem could be stack overflows due to a

  1655   lack of tail recursion optimisation. On the other hand you can

  1656   simulate laziness using generators.

  1657 

  1658   Cheers,

  1659   Thorsten 

  1660 \end{mybox3}

  1661 

  1662 Trees \url{https://youtu.be/7tCNu4CnjVc}

  1663 

  1664 Laziness \url{https://youtu.be/5jwV3zxXc8E}

  1665 

  1666 \end{frame}

  1667 

  1668 \begin{frame}[c]

  1669 \begin{mybox3}{}

  1670   What suggestions do you have for us to get the most out of this

  1671   module, especially in the online format? I.e. form discussion

  1672   groups, will you have office hours?

  1673 \end{mybox3}

  1674 

  1675 \small

  1676 \hfill $\Rightarrow$\mbox{} Discussion Forum on KEATS

  1677 

  1678 \hfill online tutorial sessions

  1679 

  1680 \hfill ???

  1681 

  1682 \hfill PL-groups for ``exotic'' langs

  1683 \end{frame}

  1684 

  1685 \begin{frame}[c]

  1686  \small

  1687 \begin{mybox3}{}

  1688 Where do most students struggle with this module? What will the format

  1689 of the exam be? What is the most efficient way of studying for the

  1690 exam? There are plenty of resources available on KEATS, but is there

  1691 anything else you'd recommend us to study? Although (just by skimming

  1692 the headings) the module seems to be a combination of practical and

  1693 theoretical matters, exactly in what field would the syllabus be

  1694 applied? Besides these questions and the ones other students asked, is

  1695 there anything else we should know? Thank you!

  1696 \end{mybox3}

  1697 \end{frame}

  1698 

  1699 

  1700 \begin{frame}[c]

  1701 \end{frame}

  1702 

  1703 \begin{frame}[c]

  1704 \end{frame}

  1705 

  1706 \begin{frame}[c]

  1707 \end{frame}

  1708 

  1709 \begin{frame}[c]

  1710 \end{frame}

  1711 

  1712 \begin{frame}[c]

  1713 \end{frame}

  1714