This course provides an introduction to algorithms, including their design, analysis, implementation, and application. It is designed for use in an intermediate-level introduction to algorithms course. We provide the Python implementations for almost all data structures and algorithms discussed. Two major types of algorithms are covered in this course: the basic algorithms (such as traditional searching and sorting) and several classic data mining algorithms used in data science.

This course has several goals for students, including a) being familiar with Python programming language, b) using Python to implement several basic data structures (such as stack, queue, tree) and several basic algorithms (such as different types of sorting and searching algorithms), c) understanding the implementing data mining algorithms, and d) applying the algorithms to real-world problems.

Students are required to demonstrate their capability to solve real-world problems by using appropriate data structures and algorithms. Students are encouraged to practice and solve problems in LeetCode. Note that you need to submit your homework and assignments via an online submission system, and you should do the homework and assignments by yourself alone without discussing with your classmate.

Class Info

• Instructor: Shun-Wen Hsiao, NCCU MIS Dept., hsiaom at nccu.edu.tw
• Lectures: Thursday D56 (13:10~16:00)
• Classroom: 商館 260209 學思 040306 資訊 140105
• TA: 李宜臻 (106356021)
• Office Hours: By appointment only.
• GitHub: https://github.com/hsiaom26/Algorithms
• Homework Submission: TBA.

Announcements (Spring 2018)

• 2/26: For students who enroll this class, you must install a Python execution environment to practice writing codes and thinking how algorithms work. Please see the document Python Execution Environment (pdf), and try to follow the steps in Section 1.1 on your own computer. I will go over the installation twice in 3/01 and 3/08 (in case you miss the class) to make sure all students have a Python execution environment.
• 3/06: Classroom changed! Please go to 040306 (學思樓 306 教室) directly.
• 3/21: Classroom changed again! Please go to 140105 (資訊大樓 105 教室) directly.
• 3/22: Upload you homework at ftp://140.119.19.178, the id and the password will be announced in the class. If you have any problem of uploading your homework, please email TA before the deadline. You should upload your homework in .py format (NOT ipynb). Your filename should be your student ID plus a version number, for example, 106306000-1.py. We will grade your homework by using your latest submitted py file before the deadline.
• 5/15: The midterm exam is on line.
• 5/15: An bonus is announced for the LightsOut.ipynb. If you can design a better algorithm t o find a solution of lights out, please submit your answer to TA before 5/23 23:59. You can get extra 3 points.
• 6/10: HW-06 is updated due to some errors.

Course Objectives & Learning Outcomes

• To review the ideas of programming, and problem solving.
• To understand abstraction and the role it plays in the problem-solving process.
• To understand and implement the basic algorithms and data mining algorithms.
• To be able to estimate the efficiency of an algorithm and try to improve it.
• To review the Python programming language.

• Students have knowledge of the most common abstractions for data collections (e.g., stacks, queues, lists, trees) by using Python.
• They understand algorithmic strategies for producing efficient realizations of common data structures.
• They can analyze algorithmic performance, both theoretically and experimentally, and recognize common trade-offs between competing strategies.
• They can wisely use existing data structures and algorithms found in modern programming language libraries.
• They have experience working with concrete implementations for most foundational data structures and algorithms.
• They can apply data structures and algorithms to solve complex problems.

Schedule (Spring 2018)

1. 3/01: Programming and Data Science. Introduction (slides) Python Execution Environment (pdf)
2. 3/08: Python Environment and Python Basic Operation. Python-LanguageReference.ipynb Python-Built-inFunctions.ipynb
   • Note: classroom changed! Please go to 040306 (學思樓 306 教室) directly.
3. 3/15: Python Data Structures and Python I/O and Exception. Python-Built-inTypes.ipynb Python-IO&EE.ipynb
4. 3/22: Object-Oriented Programming (Stack.ipynb) and LeetCode (https://leetcode.com/) Example (771. Jewels and Stones and my solution in ipynb)
   • Note: classroom changed again! Please go to 140105 (資訊大樓 105 教室) directly.
   • HW-01 (Due on Wednesday, 28 March 2018 at 23:59. You must upload your home work via FTP. Please see the announcement.)
5. 3/29: Recursion and Algorithm Analysis. Recursion.ipynb Complexity.ipynb
   • HW-02 (Due on Wednesday, 11 April 2018 at 23:59.)
6. 4/05: No class.
7. 4/12: Sorting and Searching -I. Search.ipynb Sorting.ipynb Hash.ipynb
8. 4/19: Sorting and Searching -II
   • HW-03 (Due on Wednesday, 25 April 2018 at 23:59.)
9. 4/26: Midterm. Here is the pdf.
10. 5/03: Trees and Tree Algorithms. Trees.ipynb Trees2.ipynb AVL_rotation (pdf)
    • HW-04 (Due on Wednesday, 16 May 2018 at 23:59.)
11. 5/10: HuffmanEncoding.ipynb, DynamicProgramming.ipynb (Knapsack, Local/Global Sequence Alignment)
    • Here is an interesting problem: LightsOut.ipynb
    • Here is an interesting website: Dictionary of Algorithms and Data Structures
12. 5/17: String Matching (KMP.ipynb, AhoCorasick.ipynb, aho.pdf), Majority.ipynb (bucket sort, k-th smallest, celebrity), Minimum_Edit_Distance.ipynb.
    • HW-05 (Due on Wednesday, 24 May 2018 at 23:59.)
    • Q: A binary search in sequence of unknown size?
13. 5/24: Graph Algorithm
    • Basics: Vocabulary and Definitions, Eulerian Path (Königsberg Bridges), Graph Abstract Data Type
    • Implementation: An Adjacency Matrix, An Adjacency List, A Python Implementation
    • Search: Breadth First Search (queue) & Depth First Search (stack), BFS Analysis, DFS Analysis.
      • Applications of Depth First Search: Detect Cycle, Path Finding, Topological Sorting, Bipartite Graph, Solving Mazes.
      • Applications of Breadth First Traversal: Shortest Path, Web Crawler, Social Network, Maximum Flow.
    • Shortest Path: Dijkstra’s Algorithm, Analysis of Dijkstra Algorithm.
    • Minimum-Cost Spanning Tree: Prim’s Spanning Tree Algorithm.
14. 5/31: Graph Algorithm II
    • Top 10 Graph Algorithms you must know before Programming Interview: Youtube
    • Algorithms and data structures for Interview preparation: Youtube
    • Network Flows: Maximum Flow Minimum Cut
    • HW-06 (Announced on 6 June; Due on Thursday, 14 June 2018. Please hand-in a hard copy in the class.)
      • Note that HW-06 is updated in 6/10 due to some errors.
15. 6/07: Data Mining Algorithm: DM-0, DM-DT, DM-PCA, DM-AR
    • Classification: Regression (Linear, Logistic), Decision Tree (Information Gain, Gini, Chi, Variance)
    • Clustering: UPGMA, k-means
    • Dimension Reduction: PCA + LDA
    • Association Rule (Orange has an add-on for generating association rules.)
16. 6/14: Data Mining Tools
    • Orange3 (Youtube), KNIME (Youtube), Alteryx, RapidMiner.
    • HW-07 (Announced on 6 June; Due on Thursday, 21 June 2018. Please hand-in a hard copy in the class.)
    • Gephi is an visualization and exploration software for all kinds of graphs and networks. (Gephi needs Java run-time.)
      • Social Network Analysis: Cohesion, Centrality(Degree, Closeness, Betweenness, Eigenvector), Community (Modularity). (Here is the explanation on Youtube.)
17. 6/21: Cryptography
    • Cryptographic hash function: MD5, SHA256
    • Message authentication code: MAC, HMAC
    • Symmetric-key algorithm: AES example
    • Public-key cryptography: RSA example
    • Digital Signature
18. 6/28: Final

Grading Policy

• Homework (30%): programming exercises and essays
• Participation (5%): attendance and discussion
• Term Project (15%): implement a data analysis application
  • Form a group of (max) three students, and solve a classification or regression problem by using any Internet data (or http://vincentarelbundock.github.io/Rdatasets/datasets.html or https://www.kdnuggets.com/datasets/index.html).
  • Hand-in a hard copy of the report in 6/28. The report should includes 1) the problem you would like to solve; 2) the data you would like to analysis; 3) the algorithms you use; 4) the analysis results and the implication/insight of your analysis.
• Midterm and Final (50%)