CS/ECE 374-B Spring ’25
Introduction to Algorithms & Models of Computation
Introduction
Welcome to CS/ECE 374 (Section B), a foundational course in theoretical computer science jointly offered by the Siebel School of Computing and Data Science and the Department of Electrical and Computer Engineering at the University of Illinois. This course delves into the essential tools and techniques for understanding formal languages and automata, designing and analyzing algorithms, and exploring the limits of computation.
Key Topics: The key topics covered in this course are:
- Formal Models of Computation: Understand finite automata, Turing machines, and the Church-Turing thesis.
- Algorithm Design: Learn various paradigms such as recursive algorithms, divide-and-conquer, dynamic programming, and greedy algorithms.
- Graph Algorithms: Study fundamental graph algorithms including reachability, breadth-first search, depth-first search, shortest paths, and minimum spanning trees.
- Complexity Theory: Explore the concepts of NP-completeness, polynomial-time reductions, and undecidability.
Prerequisites: One of CS 173 (Discrete Structures) or MATH 213 (Basic Discrete Mathematics), and CS 225 (Data Structures).
Learning Outcomes: By the end of this course, students will be able to:
- Understand formal models of compution and their limitations.
- Design efficient algorithms for a variety of computational problems.
- Analyze the asymptotic running time of algorithms.
- Model computational problems using graphs and apply appropriate graph algorithms.
- Prove the correctness of algorithms and understand their limitations.
- Demonstrate an understanding of NP-hardness and undecidability through reductions.
Course Structure: The course includes lectures, discussion sessions, and hands-on assignments to reinforce the theoretical concepts covered. Active participation in all sessions is strongly encouraged to maximize learning outcomes.
Course Platforms: The course platforms are:
- Website is the primary platform for everything you need.
- Canvas to maintain the final grades.
- Gradescope to submit homework, view grades, and submit regrade requests.
- Campuswire to have class-related discussions.
- Mediaspace to view the lecture videos.
Grading
The course grade will be based on homework and exams. The weights of the various items are as follows:
- Homework: 28%. There will be 7 homework assignments in total. Each homework will have 5 problems, i.e., a total of 35 problems. We will drop the 7 lowest-scoring problems. Hence, each counted problem will carry 1% of the course grade.
- Exams: 72%. There will be 5 exams in total. Four non-cumulative exams, called midterms, will take during class time. An optional cumulative final exam will be held according to the final exam schedule determined by the registrar. Each exam (midterm or final) will count for 18% of the final grade.
The final letter grades will be assigned as follows based on your course score:
[90, 100] | [80, 90) | [70, 80) | [60, 70) | [0, 60) |
---|---|---|---|---|
A | B | C | D | F |
Note that
- Adjusting the cutoffs so that the final grade is better than it would be based on the initial cutoffs, but never worse.
- Increasing the raw scores based on the overall class performance.
Textbooks and References
The course textbooks are:
- [SITC] Michael Sipser, Introduction to the Theory of Computation, 3rd Edition.
- [JEAL] Jeff Erickson, Algorithms, 1st Edition.
Additional references are:
- [ATLC] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, Automata Theory, Languages, and Computation, 3rd Edition.
- [CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 3rd Edition.
- [KTAD] Jon Kleinberg and Éva Tardos, Algorithm Design, 1st Edition.
- [TACP] Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd Edition.
Absence Policy
One of the great aspects of the college experience is that it is truly what you make of it. Attendance will not be enforced in this class. However, attending lectures is crucial as exams will cover both lecture content and assigned readings. You are responsible for all lecture materials and any announcements made in class, regardless of your attendance.
Please communicate with the instructor and/or the teaching assistant if you become ill or emergencies arise so that we will be aware of your circumstances. Article 1, Part 5 of the Student Code outlines those circumstances in which a student may be eligible to obtain a letter from the Office of the Dean of Students for absences.
Academic Honesty
The usual academic integrity policies apply. Students are expected to behave in a professional & ethical manner, and your work should be your own. At minimum, plagiarism or cheating will result in a zero for the relevant assignment/exam.
Please refer to Article 1, Part 4 – Academic Integrity Policy and Procedure of the Student Code of the University of Illinois Urbana-Champaign for relevant definitions and policies.
Accessibility and Disability Accommodations
To obtain disability-related academic adjustments and/or auxiliary aids, students with disabilities must contact the course instructor as soon as possible and provide the instructor with a Letter of Academic Accommodations from Disability Resources and Educational Services (DRES).
Please refer to Disability Resources and Educational Services (DRES) at the University of Illinois Urbana-Champaign for details.
Community of Care
As members of the Illinois community, we each have a responsibility to express care and concern for one another. If you come across a classmate whose behavior concerns you, whether in regard to their well-being or yours, we encourage you to refer this behavior to the Connie Frank CARE Center (formerly the Student Assistance Center) in the Office of the Dean of Students. You may do so by calling 217-333-0050 or by submitting an online referral. Based on your report, staff in the Student Assistance Center will reach out to offer support and assistance
Disruptive Behavior
Behavior that persistently or grossly interferes with classroom activities is considered disruptive behavior and may be subject to disciplinary action. Such behavior inhibits other students’ ability to learn and an instructor’s ability to teach. A student responsible for disruptive behavior may be required to leave class pending discussion and resolution of the problem and may be reported to the Office for Student Conflict Resolution for disciplinary action.
Emergency Response Recommendations
Emergency response recommendations and campus building floor plans can be found at the following website: https://police.illinois.edu/em/run-hide-fight/. We encourage you to review this website within the first 10 days of classes.
Religious Observances
It is the policy of the University of Illinois Urbana-Champaign to reasonably accommodate its students’ religious beliefs, observances, and practices that conflict with a student’s class attendance or participation in a scheduled examination or work requirement, consistent with state and federal law. Students should make requests for accommodation in advance of the conflict to allow time for both consideration of the request and alternate procedures to be prepared. Requests should be directed to the instructor. The Office of the Dean of Students provides an optional resource on its website to assist students in making such requests.
Other Policies
The Grainger College of Engineering at Illinois is committed to the creation of an anti-racist, inclusive community that welcomes diversity along a number of dimensions. The effectiveness of this course is dependent upon each of us to create a safe and encouraging learning environment that allows for the open exchange of ideas while also ensuring equitable opportunities and respect for all of us. Everyone is expected to help establish and maintain an environment where students, staff, and faculty can contribute without fear of personal ridicule, or intolerant or offensive language.
If you witness or experience racism, discrimination, micro-aggressions, or other offensive behavior, you are encouraged to bring this to the attention of the course director if you feel comfortable. You can also report these behaviors to Campus Belonging Resources.