3:30-4:50 PM on Tuesdays and Thursdays

**Course Description: **
This course will introduce students to algorithm design, computer programming, and SQL queries. It will provide the fundamental methods, concepts and principles of these topics to give students enough breadth to use these techniques in their jobs and to prepare them to pursue advanced topics in these areas. There will be weekly programming assignments to implement algorithms and SQL covered in the class.

**Prerequisite:** Basic programming skills, algebra and basic calculus, basic real analysis.

**Undergraduate Credit**- Homework (weekly assignments) (40%)
- 2 Midterm exams (15% each)
- Final exam (30%)
**Graduate Credit**- Homework (weekly assignments) (30%)
- 2 Midterm exams (12.5% each)
- Final exam (25%)
- Project (20%)

- Algorithm Design: Big O Notation, Growth of Functions, Greedy Algorithms, Divide and Conquer, Dynamic Programming, P/NP and Computational Intractability
- Programming in C++: Variables, Statements, Functions, Pointers, Dynamic Memory Allocation, Libraries, File I/O, etc.
- SQL Queries: Database Design and E/R Model, Relational Model , Basic SQL, Intermediate SQL

There will be roughly 11 homeworks. The lowest homework score will be dropped. A project can have at most 3-4 students. More details in class.

- Algorithm Design by Kleinberg and Tardos. Pearson Education (2013)
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. 3rd Edition, MIT Press (2009)
- Database System Concepts by Silberschatz, Korth, and Sudarshan. 6th edition, McGraw-Hill (2010)
- Database Management Systems by Ramakrishnan and Gehrke. 3rd Edition, McGraw-Hill (2002)
- Starting Out with C++ from Control Structures to Objects, 8th Edition, by Tony Gaddis (2014)
**Lectures notes/slides from relevant courses**, e.g., Lecture Slides for Algorithm Design, Introduction to Algorithms, CS225@Illinois- For
**programming in C++**, you may refer to the following tutorials: C++ Tutorial, C++ Lessons, Introduction to C++, C++ reference, learncpp.com

(The lecture slides and recordings will be posted on Compass.)

- Aug 23: Stable Matching
- Chapter 1.1 of Algorithm Design
- Aug 25: C++: Introduction, Control Structures, Conditionals
- Refer to the resources provided above
- Aug 30: Algorithm Analysis: Growth of Functions, Big O Notation
- Chapter 2.1-2.2 of Algorithm Design
- Sep 1: C++: Loops
- Sep 6: Asymptotic Order of Growth, Common Running Time
- Chapters 2.2 of Algorithm Design
- Sep 8: C++: Functions
- Sep 13: Graphs: BFS, Testing Bipartiteness
- Chapters 3.1, 3.2, 3.4 of Algorithm Design
- Sep 15: C++: Arrays, File Operations, Random Numbers
- Sep 20: Greedy Algorithms: Scheduling
- Chapters 4.1-4.2 of Algorithm Design
- Sep 22: C++: Scope, Pointers, Dynamic Memory Allocation
- Sep 27: Greedy Algorithms: Shortest Path, Minimum Spanning Tree
- Chapters 4.4-4.5 of Algorithm Design
- Chapter 14.5 of Introduction of Algorithms
- Sep 29: C++: Implementation of Stable Matching
- Oct 4: Review Class
- Oct 6: C++: Data Structures and Implementation of Graph Algorithms
- Oct 11:
**Midterm 1** - Oct 13: Database Design and Relational Model
- Oct 18: Greedy Algorithms
- Oct 20: Intro to SQL
- Oct 25: Dynamic Programming Paradigm
- Chapter 15.1 of Introduction to Algorithms
- Oct 27: SQL
- Nov 1: Dynamic Programming: Knapsack
- Chapters 6.1-6.2, 6.4 of Algorithm Design
- Nov 3: SQL
~~Nov 8:~~Holiday- Nov 10: SQL
- Nov 15:
**Midterm 2** - Nov 17: Database Design: Entity-Relationship Model
~~Nov 22:~~Fall Break~~Nov 24:~~Fall Break- Nov 29: Divide and Conquer Paradigm: Recurrence Relation, MergeSort, Integer Multiplication, Binary Search
- Chapter 5.1, 5.2, 5.5 of Algorithm Design
- Dec 1: SQL
- Dec 6: NP and Computational Intractability, NP-complete Problems
- Chapter 8.1, 8.2, 8.4 of Algorithm Design
- Dec 12:
**Final Exam (1:30-4:30 PM)**