You are here! Primary information source for the course: course info, public logistics, lecture slides, worksheets, syllabus.
I. Instructors & Course Details
- Instructor
-
Jonathan Liu jonliu@uic.eduOffice Hours: Wed 1:30-2:30pm, CDRLC 3450Office Hours: Th 3:30-5pm, CDRLC 3450All Piazza questions asked on/before office hours will also be answered ASAP (though in-person OH will take precedence).Want to meet another time? Send me an email!
- Lecture
- Tuesdays & Thursdays, 9:30–10:45am
Lecture Center D | Room D001
- Canvas Course Site
- https://canvas.uic.edu/courses/56572
Students are expected to log into the course site regularly to learn about any announcements or developments related to the course. See Course Information below for all websites used by the course, and the purpose of each. For all technical questions about Canvas, email the Learning Technology Solutions team at LTS@uic.edu.
- Course Modality and Schedule
- Tuesdays & Thursdays, 9:30–10:45am
In-Person: Lecture Center D | Room D001Note: This course is cross-listed as CS 401 (CRN 10671/20264) and MCS 401 (CRN 12375/20265).
II. Course Information
Catalog Course Description and Prerequisite Statement
Design and analysis of computer algorithms. Divide-and-conquer, dynamic programming, greedy method, backtracking. Algorithms for sorting, searching, graph computations, pattern matching, NP-complete problems.
Prerequisite(s): Grade of C or better in MCS 306 or CS 251. If you are a graduate student who has not taken one of these classes, you will still be expected to have mastery over material covered in these classes and their prerequisites; in particular, discrete mathematics (particularly functions, set theory, proofs, and induction) and basic data structures (including recursion and graphs).
- Course Goals and Learning Outcomes
- The aim of this course is to develop your ability to design,
evaluate, and communicate about algorithms for tackling real-world problems.
Learning outcomes
In order to do so, you will learn to:
- Model real-world problems as computational problems with appropriate levels of abstraction
- Consider the implications of real-world modeling decisions
- Relate computational problems to previously-seen ones and write appropriate reductions
- Determine whether a given problem is feasible to compute efficiently
- Determine an appropriate algorithm design paradigm for a given problem
- Design an algorithm using a number of different algorithm design paradigms
- Prove that an algorithm produces the optimal answer to a problem
- Analyze the asymptotic runtime of an algorithm
- Important Links
-
Homework submissions (and feedback), occasional in-class activities, exam grades.
Non-public material — problem sets and solutions.
Forum for announcements and discussion.
- Recommended Textbooks
-
This course roughly follows three textbooks. You are not required to buy a textbook. Lecture slides will all be shared, and problem sets are self-contained.
Still, while the course notes posted will be sufficient, it can be helpful to see content explained in a different way and to have more practice problems and examples than can be covered in class. Useful readings from these resources will be posted to the course schedule.
AlgorithmsMy favorite textbook, in no small part because it is the book that I learned from so I am biased. I think the explanations here are clear and well-motivated, but can get a bit in the weeds sometimes.Free Online Copy →AlgorithmsFree online. Excellent problem sets to practice on. Jeff has strong feelings about algorithms education and his textbook is full of his personality. For what it's worth, Jeff is an expert and I largely agree with his opinions.Algorithm DesignI like the way this book approaches and illustrates its problems.
Respect for Copyright
Please protect the copyright integrity of all course materials and content. Please do not upload course materials not created by you onto third-party websites or share content with anyone not enrolled in our course.
III. Course Policies & Classroom Expectations
This course is graded using standard letters (e.g. a B is 80%-90%). In the event that coursework is more difficult than intended, grade cutoffs will be made more generous. Individual assignments will not be curved. Test statistics are not released. The course is small, so your grade never depends on how your peers perform.
Your grade is composed of three buckets: Homework, Exams, and a Project. Click any row below for more detail about the policies.
Homework—A low-stakes practice
opportunity, with lenient policies to support that.
28%
This course is divided into 6 units, each lasting around 2 weeks. Homework is assigned on the second Tuesday of each unit, and due on the first Friday of the next unit. There is also an introductory Homework 0.
Homework is a low-stakes opportunity for you to practice the material. All of the policies outlines below are in service of that goal.
Because problem sets are a chance for you to learn and practice, you will be allowed to resubmit each problem set. You may resubmit as many times as you would like for a week after the due date, so that official homework solutions may be released to study with. Note that they may take a few days to be graded so it would be prudent to resubmit early, especially if you are unsure about your answer. Your resubmission should have your work for every question, regardless of whether it has changed. That said, please make very clear which questions have been changed and which have not. For any question you would like to resubmit, the resubmission must contain the following:
- Your original answer.
- A description, in your own words (don't just copy what the grader wrote!), of what was incorrect about the original answer, and why that occurred. Was it a misunderstanding of a term or concept, or perhaps just a calculation error? This is an opportunity for you to learn and reflect, so your score won't depend on how "good" the reason is. However, you must have made a "reasonable" attempt on your first go -- an honest but entirely incorrect attempt is fine, as is some scratch work demonstrating that you've tried the problem, but your resubmission won't be accepted without evidence that you made an attempt the first time.
- Your updated answer to the question. Any substantial change to your original answer should be justified by your description above.
Life happens, and sometimes you need to submit homework a bit late. That's totally fine with me. I'd also rather you take your time and do it properly than rush through it to meet the deadline. However, I can't grant indefinite extensions, because I need you to keep up in this fast-paced course. With that in mind, here's what you should do based on the amount of extra time you think you'll need.
- Less than two days
- Fill out this form as soon as you decide you'll need the extension. The extension will be granted.
- Up to 5 days
- Email me with the situation and how many days you need. I will always grant the extension. I just want to know what's going on and that you have a plan to finish it soon.
- Longer
- Email me and we'll meet to set up a plan so you don't fall behind.
Please feel free to collaborate with others! Working in groups is a great way to share resources, keep each other on track, and develop an overall support system. Learning to productively work in groups by articulating your ideas and processing others' is incredibly valuable as well. However, all submitted solutions should be entirely written by you alone. You should never read the solutions your collaborators intend to submit, or even drafts of those solutions. You must include a list of your collaborators in your submission.
Also, make sure to be aware of your individual capabilities. Working productively in groups is an incredibly important skill, but the primary goal of this class is still to develop your individual ability to reason about algorithms. If you're worried that you're getting carried along by your study group, I'd recommend working on some sample non-homework problems on your own for a low-stakes gauge of your abilities. Of course, these non-homework problems and their solutions can also be discussed freely at office hours!
You should treat all outside resources (LLMs, the internet) the same way. The most important policy is that you should report your use. There will be a section for this in each homework.
- DO
- Ask it to re-explain a topic you didn't understand in class. Or, even better, ask to explain a topic to it and have it judge your understanding.
- DO
- Ask it to generate practice problems for you.
- DO
- Ask it to write out a solution to a non-graded problem (either that it generated or that you found), but make sure to attempt it on your own first!
- IFFY
- Ask it to check your solution. You can do this with an LLM, but it's much better if you do this with course staff.
- DON'T
- Ask it for solutions to homework problems.
- DON'T
- Trust its output blindly. Everyone can make mistakes sometimes, but an LLM is especially prone to writing accurate-sounding text, which is of course not enough in this class.
- DON'T
- Assume everything it states is fair game. Solutions built on theorems or ideas we didn't use may not be accepted.
Academic Integrity Policy— Adapted from Omar Ibrahim
If you have any questions or concerns, please don't hesitate to ask in lecture, during office hours, or by email.
TL;DR: Be honest, cite your sources, and if you need help, please ask me for that help. I am here to help, but I can't help if you don't ask.
If you have any doubts about whether something constitutes plagiarism, talk to Jonathan, and err on the side of caution. I will not penalize you if you tell me what happened before turning in the assignment. I will not consider it an academic integrity violation if you inform me what happened before you submit.
I strongly encourage you to use any printed, online, or living resource at your disposal to help you solve homework problems, but you must cite your sources.
- If you use an idea from a book, cite the book.
- If you use an idea from a paper, cite the paper.
- If you use an idea from Wikipedia, cite Wikipedia.
- If you use an idea from CS StackExchange, cite CS StackExchange.
- If you use an idea from another student, cite that student.
This is not an exhaustive list!
There are only two exceptions to this rule. You are not required to cite the following:
- Official course materials (lectures, lecture notes, readings, and exam solutions) from this semester
- Sources for prerequisite material (which I assume you already know)
Verbatim duplication of any source, even with proper citation, is plagiarism. In particular:
- Copying verbatim from textbook solutions,
old CS 401 solutions, or a generative AI model is plagiarism.
- Using a generative AI model to help polish your own writing is not plagiarism, as long as you explicitly declare your use of that AI in your submission.
- Using a generative AI model to polish or rewrite someone else's writing and submitting the result as your own work is plagiarism.
- Submitting work done entirely by another student is plagiarism, even if you have their permission.
- Allowing another student to copy your work verbatim is also an academic integrity violation.
- Making simple lexical changes, such as changing word order or changing variable names, still counts as "copying verbatim" for purposes of this policy. It's still plagiarism.
Classes in some other departments allow and even encourage verbatim copying in small doses. For example, if you want to claim that an expert holds an important or controversial opinion, it is usually better (more honest, more accurate) to quote them verbatim, instead of rewriting their opinion in your words. But computer science classes are different. I won't ask you to defend a hypothesis or opinion using evidence or rhetoric. What I will ask for are formal, logical, mathematical arguments. Expert opinion is irrelevant here; the math must speak for itself. In particular, I am asking you to demonstrate your expertise in formal, logical, mathematical reasoning and communication. You can only demonstrate expertise in something by actually doing it.
That said, if you want to use an algorithm from the textbook, lectures, or previous homeworks in your solution, just use it (and cite it) and carefully describe any necessary changes.
I have listed a (relatively) short list of “common” smaller ways that people plagiarise – there are a number of more egregious ways to violate the university's academic integrity policies, such as collaborating with or copying from another student during an exam, hiring an impostor to submit homework or take exams for you, falsely claiming to have submitted a homework or taken an exam, and modifying or destroying other students' graded work. Just because something is not explicitly listed in this document does not automatically make it okay; please use common sense.
Given all the hype around ChatGPT and similar AI language models, many students are tempted to use them to “help” with homework. As policy, I am treating language models just like every other source—you are welcome to use it, provided you cite it and write your answers yourself in your own words—but I also want to caution you about relying on them too much.
ChatGPT and similar models are designed to produce plausible-looking text. Despite breathless language to the contrary in innumerable press releases, ChatGPT does not “know” or “understand” anything; anyone who says differently is selling something. A good high-level summary of the problem that ChatGPT solves, over and over again, is “Here are seven consecutive words from a sentence; what's the most likely eighth word?” Basically, it's a grownup version of Dissociated Press.
You should think of ChatGPT as an incredibly imaginative toddler. They're very good at telling stories, and can expound—fluently and authoritatively—about any topic you give them but in fact, everything they “know” about the topic comes from some vague snatches of words they heard adults around them say. Sometimes our toddler gets lucky and says the right thing by accident – a broken clock is right twice a day – but as a rule, they're just saying words that sound like they could plausibly go together. In particular, even for topics where they're likely to mirror the right high-level intuition, unless they are directly quoting something that it's heard before (and therefore, by my definition, plagiarising, since ChatGPT isn't so great about the whole cite your sources thing), the fine details are likely to be fictional or incoherent.
You should also remember that ChatGPT was trained on text from the internet; the influence of large crowd-sourced sites like Geeks4Geeks and StackExchange—whose content quality can be charitably described as high-variance—is quite clear. Relying on ChatGPT is roughly equivalent to relying on the average self-proclaimed internet expert, or perhaps more accurately, on the average self-proclaimed internet expert's parrot. (More specialized models, trained on more carefully curated data and able to check their own work, yield better solutions for simple math and programming problems, but even for those simple problems, “better” is still not good or correct.)
That doesn't mean you can't use ChatGPT (or Geeks4Geeks, or any other questionable source) to help you solve homework problems. After you make a good-faith effort—at least a couple of hours—to make progress on your own, then it can be useful to ask ChatGPT, and then try to figure out what's wrong with ChatGPT's answer. Once you understand what ChatGPT did right and wrong, you're in a better position to write your own answer, in your own words.
In fact, this is the approach I would suggest for any source, including the official course materials. Work on your own first, assume that your source has errors, find those errors (or prove to yourself that there are no errors), then go back to working on your own. (Hopefully the official course materials have fewer bugs than ChatGPT's output, but yes, they have bugs.)
You are strongly encouraged to seek out general resources beyond official course resources (other textbooks, lecture notes, etc.) — very often it takes two or three different explanations for a concept to click, so finding different explanations is a good thing — with the following caveats:
- Definitions and terminology can differ significantly (and subtly!) depending on the author. Be careful that other resources are saying what you think they are saying, and if something conflicts with what I teach in class, I will consider what I teach in class to be correct and anything else incorrect.
- You may not search with the intent of finding a solution to a specific homework problem (see below).
- You may not use commercial tutoring resources like Chegg for the problems I ask, nor post course materials or your answers to those websites.
While you are permitted to seek out general resources, you may not search intending to find answers to the problems I ask you on homeworks. I choose and design problems for their pedagogical value; the number of pedagogically-valuable problems is limited for some of these topics, so similar problems are likely to appear elsewhere.
- You may not use a written solution for an equivalent problem as a resource, but you may use a written solution for different problems on the same topic (i.e., other divide and conquer proofs are a fine resource).
- You may not post these problems on the internet (e.g. on Chegg, Reddit, or other sites).
Almost every instance of plagiarism I have seen was motivated by a combination of two factors.
The student feels overwhelming pressure to improve their performance, despite gaps in their understanding. The student might be overwhelmed by work in other classes, or financial pressure to graduate, or parental/cultural expectations. This might be the hardest course the student has ever taken, and their merely good performance is a blow to their aspirations or self-image. The student may be suffering from Impostor Syndrome, the feeling that they really aren't good enough to be here (despite evidence to the contrary), and that their fraud will be uncovered if they admit that they can't do something. The student might have trouble with English, and therefore worries that rewriting someone else's text would distort the meaning. Perhaps the student is dealing with depression, serious illness, divorce, or a death in the family. Or maybe the student simply sees no way to satisfy the instructor's unreasonable or unclear expectations without cheating.
- If you find yourself in this situation, ask for help! If you need help understanding the material, come to office hours, ask questions in class, talk to your fellow students. I will even make extra appointments to help guide you through the material or give you feedback on tentative solutions, but only if you ask. (But please remember that my goal is to help you master the material, not just to help you get a better grade.)
- If you think a homework problem is unclear, please ask for clarification. Your confusion might indicate a gap in your understanding of the course material, but it might also indicate that the question is poorly stated, unfairly hard, or even impossible. My job is to help you learn the material; please let me know if I'm not doing my job.
- I do expect solutions to be written in clear, coherent English. If you are thinking of copying someone else's words because you are uncomfortable with English, you are probably better off stepping back to improve your English skills might be more important than getting a good grade in this course.
- Asking for help does not make you “look stupid”. Quite the opposite — it means you are smart enough to recognize your own limitations and work to overcome them. Asking for clarification is not an insult to the instructor. Again, it's the opposite — questions are valuable feedback that I can use to teach more effectively. Everyone suffers from Impostor Syndrome occasionally, including your professors. Most importantly, please remember that your grade is not a statement about your intelligence, your potential for success, or your worth as a human being; it's only feedback about your mastery of the course material.
- If your situation is very serious, or not directly related to this class, you may prefer to discuss your situation with your department or college advisor, a family member, a trusted friend, or the counseling center, but please talk to someone.
The student is used to an academic culture where plagiarism is tolerated or even encouraged. Maybe they come from a high school with litigious parents who discourage teachers from punishing cheaters. Maybe they come from a country where students are expected to parrot back their instructors' exact words to demonstrate understanding. Maybe they've been trained by their previous classes to optimize points, even at the expense of honesty, instead of learning. Maybe cheating was inconsistently or ineffectively enforced in their past classes; they've seen cheating students succeed (getting higher grades, or even better jobs) where honest students have suffered.
- Please be aware that my standards for academic integrity may be different than what you're used to. This point is especially important for international students. The standards I apply in this class are a proper subset of the standards applied to Illinois faculty and most other professional scientific researchers. (Fortunately, we don't have to worry about authorship and author ordering policies, accurate recording and reporting of experimental results, or ethical issues with animal test subjects.)
- My job as an instructor is to help you master the course material. I ask that you write everything yourself so that I can make an honest assessment of your mastery of the course material, and therefore give you useful feedback. I allow wide latitude in choosing the resources you need to learn, because I believe that freedom will help you learn more effectively. I trust that you will use those resources responsibly and ethically. Plagiarizing other people's work to improve your grade is an abuse of that trust. It is unfair to yourself, to me, and to your fellow students.
- I am painfully aware of differences in cheating policies and their enforcement in different classes, both within and outside the computer science department. Within the guidelines of the Student Code, the university gives faculty broad discretion (under the rubric of academic freedom) in defining what constitutes “cheating” and how strictly cheating policies are enforced. Sometimes these differences lead students to believe that cheating policies are overly restrictive or inconsistent, and so can be justifiably ignored.
- I believe that my policies are fair, but even with the best of intentions, people make mistakes. If you believe that any policies in this course are unclear, unreasonable, or inconsistently applied, I strongly encourage you to voice your concerns to me and/or the department administration. If you wish to complain anonymously, feel free to contact the department administration directly.
Very rarely, students cheat simply because they want a good grade (or a degree) at all costs, with no thought whatsoever for learning or fairness. I have absolutely no sympathy for these students. You have every right to rob yourself of the educational opportunity you (or your parents) have paid for, but don't expect me to help you.
Exams—Demonstrate your learning.
Buffered by participation.
60%
This class has a midterm and a final exam. The final is cumulative, but will be more focused on the material taught after the midterm. For each exam, you will be able to bring in one hand-written cheat sheet. No other materials or aid will be permitted during the exams. The midterm will occur during lecture.
Each instance of participation will be worth half a point of extra credit on the upcoming exam. Participation refers to attending lecture, attending office hours, or asking/answering a course content-related question on Piazza. You are capped at 10 points per exam.
Project—A long open-ended algorithm
design task.
12%
Details on the project will be posted later in the term.
If you are an undergraduate student, you are welcome to work on the project with a partner. If you are a graduate student, you must complete it alone. The project will be introduced after the midterm, and I will ask for your teams then.
IV. Course Schedule
See the course schedule.
V. Accommodations
Disability Accommodation Procedures
UIC is committed to full inclusion and participation of people with disabilities in all aspects of university life. If you face or anticipate disability-related barriers while at UIC, please connect with the Disability Resource Center (DRC) at drc.uic.edu, via email at drc@uic.edu, or call (312) 413-2183 to create a plan for reasonable accommodations. To receive accommodations, you will need to disclose the disability to the DRC, complete an interactive registration process with the DRC, and provide me with a Letter of Accommodation (LOA). Upon receipt of an LOA, I will gladly work with you and the DRC to implement approved accommodations.
Religious Accommodations
Following campus policy, if you wish to observe religious holidays, you must notify me by the tenth day of the semester. If the religious holiday is observed on or before the tenth day of the semester, you must notify me at least five days before you will be absent. Please submit this form by email with the subject heading: “YOUR NAME: Requesting Religious Accommodation.”
Any Other Accommodations: Let Me Know!
We recognize that our students come from varied backgrounds and can have widely-varying circumstances. We also acknowledge that the circumstances of this particular semester may bring unique challenges. If you have any unforeseen circumstances that arise during the course, please do not hesitate to contact the instructor to discuss your situation. The sooner we are made aware, the more easily we can provide accommodations.
Typically, extenuating circumstances include work-school balance, familial responsibilities, health concerns, or anything else beyond your control that may negatively impact your performance in the class. Additionally, while some amount of “productive struggle” is healthy for learning, you should ask the course staff for help if you have been stuck on an issue for a very long time.
Life happens! While our focus is providing an excellent educational environment, our course does not exist in a vacuum. Our ultimate goal as a course staff is to provide you with the ability to be successful, and we encourage you to work with us to make that happen.
VI. Classroom Environment
- Inclusive Community
- UIC values diversity and inclusion. Regardless of age, disability, ethnicity, race, gender, gender identity, sexual orientation, socioeconomic status, geographic background, religion, political ideology, language, or culture, we expect all members of this class to contribute to a respectful, welcoming, and inclusive environment for every other member of our class. If aspects of this course result in barriers to your inclusion, engagement, accurate assessment, or achievement, please notify me as soon as possible.
- Name and Pronoun Use
- If your name does not match the name on my class roster, please let me know as soon as possible. My pronouns are he/him. I welcome your pronouns if you would like to share them with me. For more information about pronouns, see this page: https://www.mypronouns.org/what-and-why.
- Community Agreement/Classroom Conduct Policy
-
- Be present by turning off cell phones and removing yourself from other distractions.
- Be respectful of the learning space and community. For example, no side conversations or unnecessary disruptions.
- Use preferred names and gender pronouns.
- Assume goodwill in all interactions, even in disagreement.
- Facilitate dialogue and value the free and safe exchange of ideas.
- Try not to make assumptions, have an open mind, seek to understand, and not judge.
- Approach discussion, challenges, and different perspectives as an opportunity to “think out loud,” learn something new, and understand the concepts or experiences that guide other people’s thinking.
- Debate the concepts, not the person.
- Be gracious and open to change when your ideas, arguments, or positions do not work or are proven wrong.
- Be willing to work together and share helpful study strategies.
- Be mindful of one another’s privacy, and do not invite outsiders into our classroom.
VII. Resources: Academic Success, Wellness, and Safety
We all need the help and the support of our UIC community. Please visit my drop-in hours for course consultation and other academic or research topics. For additional assistance, please contact your assigned college advisor and visit the support services available to all UIC students.
Academic Success Resources
- UIC Tutoring Resources
- College of Engineering tutoring program
- Equity and Inclusion in Engineering Program
- UIC Library and UIC Library Research Guides
- Offices supporting the UIC Undergraduate Experience and Academic Programs
- Student Guide for Information Technology
- First-at-LAS Academic Success Program, focusing on LAS first-generation students
Wellness Resources
- Counseling Services: You may seek free and confidential services from the Counseling Center at https://counseling.uic.edu/.
- Access U&I Care Program for assistance with personal hardships.
- Campus Advocacy Network: Under Title IX, you have the right to an education that is free from any form of gender-based violence or discrimination. To make a report, email TitleIX@uic.edu. For more information or confidential victim services and advocacy, visit UIC’s Campus Advocacy Network at https://can.uic.edu/.
Safety Resources
- UIC Safe App — PLEASE DOWNLOAD FOR YOUR SAFETY!
- UIC Safety Tips and Resources
- Night Ride
- Emergency Communications: By dialing 5-5555 from a campus phone, you can summon the Police or Fire for any on-campus emergency. You may also set up the complete number, (312) 355-5555, on speed dial on your cell phone.