Real sequences: recursive definition, monotonicity, convergence. Sums and series. Solution of linear recursive equations. Power series. Generating functions. Graphs: basic terminology, isomorphism, Euler and Hamilton paths, the travelling salesman problem, planar graphs. Trees: definitions, binary trees, spanning trees, Dijkstra’s shortest path algorithm. Algorithms: Ο, Ω, Θ notation, time complexity, design principles.

The course is intended to introduce students to the theoretical tools and methodologies of Computer Science at a second level. Upon completion of the course the student will have:

• a basic knowledge of the terminology and properties of graphs and trees;
• the ability to use combinatorial arguments in proofs;
• an understanding of the notion of algorithm complexity and of the basic methodologies for its calculation;
• the ability to state simple algorithms to solve elemental problems.

None required

• Κ. Rosen. «Διακριτά μαθηματικά και εφαρμογές τους», Εκδόσεις Α. Τζιόλα & Υιοί, 2008.
• Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. «Διακριτά μαθηματικά – Ενιαίο», Γ. ΔΑΡΔΑΝΟΣ - Κ. ΔΑΡΔΑΝΟΣ Ο.Ε, 2008.
• C.L. LIU. «Στοιχεία Διακριτών Μαθηματικών», Ιδρυμα Τεχνολογίας & Ερευνας-Πανεπιστημιακές Εκδόσεις Κρήτης, 2009.
• S.S. Epp, Διακριτά Μαθηματικά με Εφαρμογές. Εκδόσεις Κλειδάριθμος, 2010.
• Eric Lehman and Tom Leighton, "Mathematics for Computer Science", 2004. Διαθέσιμο μέσω του MIT OpenCourseWare.

• 5 in-class quizzes
• Final written exam

Weekly class meetings

Weekly recitations (devoted mostly to problem solving)