- How to get in touch with me: M, W: 9:00 a.m. - 10:00 a.m.; W, F: 1:00 p.m. - 2:00 p.m.; and whenever my door, D&M 422, is open- The best way to contact me: Email me, zshen@plymouth.edu, any time between 8 a.m. and 9 p.m. during the weekdays- My home page
As a critical course in the Computer Science curriculum, the objective of this course is clear and simple: Learn how to find a better, if not the "best", algorithmic solution to a realistic problem.
After (p)reviewing relevant mathematical notions, and presenting a basic analytical model for algorithms to address the issue as what is a better solution in terms of both time and space, we will present, analyze, and compare some classic algorithms for several real-life problems, including the fundamentally important sorting problem, and several graph based problems such as graph searching, shortest paths, minimum spanning trees, and, if time allows, the maximum network flow problem.
To design better algorithms, we will study various design techniques such as divide-and-conquer, greedy methods, randomization, and the increasingly important parallel programming techniques with the help of the Chapel language. We will also review various data structures that you have already studied in earlier courses, such as set, list, tree and graph. Some other related topics such as NP-completeness and approximation algorithms will also be explored.
For those who have to miss some classes or have some class notes to make up, I have included extended abstracts of my lecture notes within this syllabus. I will also make available, on Canvas, recordings of the sessions that I made in Spring 2021. Notice that those recordings will not the the same as what we will go through this semester, but might be useful.
Most of the communication regarding this class will be done through email to your plymouth address, with a subject starting with "CS3221:...", so you have to regularly check your email while taking this course.
To achieve the above learning objective, numerous homework of various difficulty degrees will be assigned within the lecture notes, and you have to submit solutions through the Canvas page. Although a student should not hand in anything unless and until s/he is reasonably sure about their correctness, the deadline to submit solutions to all the assigned homework is by 9 p.m. on the first business day in the following week, once a chapter is completed. For example, if we finish a chapter by the end of this week, the assigned homework will be handed in by 9 p.m., next Monday, January 29, 2024 since it is not a holiday.
This course will be taught in a language independent manner, in the sense that algorithms will be described in structured English and pseudocode understandable for anyone with minimum programming experience. On the other hand, a collection of rather challenging projects will be assigned when algorithms will be implemented in a certain programming language, Java for this course. Studens will also practice parallel programming techniques with Chapel. Deadlines for such assignments can also be found on the project page on Canvas.
To serve its purpose, and to be fair to everyone in the class, no proram submitted in this course may contain any complier error/warning message, when the instructor test it with a standard JDK; that program will be given a 0 otherwise.
Notice that your Java programs must contain only stanard Java features. No features that come with any IDE (Integrated Development Environment), such as IntelliJ, can be used in your programs.. If such features lead to a compiler error, you will get a 0 for that program.
This course will come with two tests and end up with a final. For details, check out the Evaluation segment of this syllabus.
Anything and everything as assigned, once submitted, will be considered final.
If you have a solid reason for a delay ("excused absences", as defined in the Plymouth State University attendence policy) of the aforementioned homework and/or project, please let me know via an email before the deadline, or as soon as possible afterwards. The work(s) invovled will not be considered when calculating your grade for this course.
To help the instructor to understand your submitted work well, anything and everything handed in for this class, including homework assignments and project reports, have to be typed using a word processor.
Anything and everything handed in for this course must be done by the signed individual. If enough evidence shows that someone is involved with "cheating", including using computer aided tools, such as CHATGPT, the case(s) will be immediately reported to the program coordinator of the Computer Science and Technology. For relevant definitions and procedural details regarding academic integrity related issues, please refer to the recently revised University's policy on Academic Integrity.
The instructor will try his utmost to be fair in grading students' work as a measurement of the quality of the submitted work in terms of its degree of meeting a clearly stated expectation. Check out the Evaluation section below for details. On the other hand, if a student believes that s/he is not given a fair grade, s/he should follow the procedure as specified in the University Fairgrading Policy to appeal the grade.
To further help students to learn the material, as constructive feedbacks, sample solutions for all the homeworks, projects, and tests, will be posted right after the submission deadline, if no students's works are pending. Beside providing an example of a correct solution to help students to achieve the expected learning objectives, such a constructive feedback also serves the purpose of justifying your grade, thus implementing the fair grading policy. As a critical step of the learning process, each and every student must go through these feedbacks, and ask the instructor for further clarification of any issue(s) s/he might have regarding an assignment, its solution, and the grade that granted for that assignment.
Plymouth State University is committed to providing students with documented disabilities equal access to all university programs and facilities. If you think you have a disability requiring accommodations, you should immediately contact the Campus Accessibility Services, located in Speare 210, to determine whether you are eligible for such accommodations. Academic accommodations will only be considered for students who have registered with the Accessibility Service. If you have a Letter of Accommodation for this course from the Campus Accessibility Services Office, please provide the instructor with that information privately so that you and the instructor can review those accommodations.
The PASS (Plymouth Academic Support Services) Office, located in Speare 209, provides tutoring and study skills information.
Student Support Foundation (SSF) provides short-term emergency financial assistance and long-term student support. Click here for more information. Student Support Foundation also runs a food pantry, located in Belknap Hall. To learn more about SSF or access the food pantry, either via open hours or a private appointment, contact the SSF advisor, at psu-ssf@plymouth.edu.
You might want to click here for additional information regarding other basic needs.
- (required) Cormen, T, H., et al, Introduction to Algorithms(Third Ed.) The MIT Press, Boston, MA, 2009.- (Optional) Khan Academy Tutorial- (required) Shen, Z., A Gentler Introduction to Chapel, Spring 2024.
-
Get it started:
- Why Algorithms?
- INFO: Computer Science at Plymouth State* RECIPE: Beef with onion and pepper* INFO: A site devoted to code education* VIDEO: What is coding?* VIDEO: How do algorithms shape our world?* READING: Why do we talk about matrix multiplication?* INFO: Roots of "program"* INFO: Various sorting algorithms* READING: Computer's help in determining the impact of CO2* READING: A Google Master beats sixty Chinese Go masters* INFO: The top 500 computers* VIDEO: Traveling salesman problem (Rated G) * READING: Traveling salesman problem (Rated R) * READING: New development of the TSP problem* READING in Depth: The exponential nature of Moore's law* READING in Depth: Moore's law is on its way out.* READING in Depth: The exponential nature of Moore's law* VIDEO: How big is one nanometer?* VIDEO: It could be really hot...* READING in Depth: Rethinking Search Engines and Recommendation Systems: A Game Theoretic Perspective* READING in Depth: Is end of programming coming?* PLAY WITH IT: Have you played with ChatGPT?* Watch: Sora by openAI- (P)review of relevant mathematical background
- INFO: How did Gauss figure out the arithmetic series?* INFO: Bike all the way up* VIDEO: Harmonic sequence in music* INFO: Evolution of NH license plates * INFO: The exponential nature of COVID 19...* INFO: A lot more details about the Fibonacci sequence* INFO: How to get a bug-free C program?* TUTORIAL: A little review of logarithms- Basics of algorithm analysis:
- INFO: Computer Science at Plymouth State* RECIPE: Beef with onion and pepper* INFO: A site devoted to code education* VIDEO: What is coding?* VIDEO: How do algorithms shape our world?* READING: Why do we talk about matrix multiplication?* INFO: Roots of "program"* INFO: Various sorting algorithms* READING: Computer's help in determining the impact of CO2* READING: A Google Master beats sixty Chinese Go masters* INFO: The top 500 computers* VIDEO: Traveling salesman problem (Rated G) * READING: Traveling salesman problem (Rated R) * READING: New development of the TSP problem* READING in Depth: The exponential nature of Moore's law* READING in Depth: Moore's law is on its way out.* READING in Depth: The exponential nature of Moore's law* VIDEO: How big is one nanometer?* VIDEO: It could be really hot...* READING in Depth: Rethinking Search Engines and Recommendation Systems: A Game Theoretic Perspective* READING in Depth: Is end of programming coming?* PLAY WITH IT: Have you played with ChatGPT?* Watch: Sora by openAI- (P)review of relevant mathematical background
- Analysis of simple sorting algorithms
- TUTORIAL: Loop vs Recursion* VIDEO: How does Bubblesort work?* VIDEO: How does Insertion sort work?* VIDEO: How does MergeSort work?* An interview with John von Neumann, who made many contributions to Computer science* VIDEO: How does Selection sort work?* VIDEO: How does QuickSort work?* A more fitting model of computation- Function growth: How much does it take, for how long?
- How much does a big MAC cost in 2024?- Probabilistic analysis: How much do you expect it to take?
- INFO: Various probabilistic distributions* INFO: How about normal distribution?* INFO: Definition of the java.util.random and an example* TUTORIAL: Probability basics* TUTORIAL: Random variables and their expected value* TUTORIAL: An introduction to Binomial theorem* INFO: Linearity of expectation of random variables* INFO: About the Harmonic Number- Faster sorting algorithms: 1. Heapsort
- Lot of application on the heap data structure- Quicksort
- INFO: Sort in java* INFO: Signature and examples of Arrays.sort() in Java* INFO: What is TimSort?* INFO: More about TimSort- Linear-time sort
- How much does a big MAC cost in 2024?- Probabilistic analysis: How much do you expect it to take?
- TUTORIAL: Loop vs Recursion* VIDEO: How does Bubblesort work?* VIDEO: How does Insertion sort work?* VIDEO: How does MergeSort work?* An interview with John von Neumann, who made many contributions to Computer science* VIDEO: How does Selection sort work?* VIDEO: How does QuickSort work?* A more fitting model of computation- Function growth: How much does it take, for how long?
**Test 1:** Wednesday, March 20, 2024, from 11:15 a.m. to 12:05 p.m..- Data structures: 1. [Basic ones:](notes/CS322/note10.pdf)(stack, queue, linked list, tree) (**Self Study, Project 5)**)- [Hashing tables](notes/CS322/note11.pdf) * Usage of a [Symbolic table](https://www.geeksforgeeks.org/symbol-table-compiler/) in a compiler* [Aho and Ullman's 2021 Turing Lecture on Compilers and other stuff](notes/CS378/turingLecture022022.pdf)* A [good read](notes/CS322/p22-neville-neil.pdf ) on algorithms, their measurement, and even hashing tables* A lot more on [hashing table](https://en.wikipedia.org/wiki/Hash_table)* [Programs = algorithms+data structures.](https://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs)- [Binary search trees](notes/CS322/note12.pdf) * INFO: What is [null pointer](notes/CS322/nullPointer.pdf ) and how to deal with it?* READING: More details of the [AVL trees](https://en.wikipedia.org/wiki/AVL_tree)- Algorithm design techniques: 1. [The greedy method](notes/CS322/note16.pdf) * INFO: [Frequency](https://www3.nd.edu/~busiforc/handouts/cryptography/letterfrequencies.html) of English letters* INFO: The real and only [Wheel of Fortune](http://www.wheeloffortune.com/) game* INFO: How to [read out](http://blog.codinghorror.com/ascii-pronunciation-rules-for-programmers/) those [ASCII](http://www.asciitable.com/) symbols?* INFO: How about [Unicode](https://home.unicode.org/)?* READING: More about [Huffman coding](http://en.wikipedia.org/wiki/Huffman_coding) **Test 2:** Wednesday, April 10, 2024, from 11:15 a.m. to 12:05 p.m..- Parallel programming fundamentals. 1. [Parallel algorithms](notes/CS322/note27.pdf) * INFO: What did a hard disk that "you've been waiting for" cost back in [1981](notes/CS322/hd1981Copy.png) and [now](notes/CS322/hd2021.png).* INFO: What happened in a Chinese [toll booth](notes/CS322/trafficJam.png) during a recent holiday?* INFO: Specification of the recent [Intel® Core™ i9-14900KS Processor](https://www.intel.com/content/www/us/en/products/details/processors/core/i9.html) and its cousins* INFO: [Sony Alpha 7R V camera with 61 MP](https://www.amazon.com/Sony-Full-Frame-Mirrorless-Interchangeable-Camera/dp/B0BKLQFFSF/ref=sr_1_2?crid=1I5GSPFC1UUKW&keywords=Sony%2B%CE%B17R%2BIV%2BA%2B61%2BMP&qid=1680875005&sprefix=sony%2B%CE%B17r%2Biv%2Ba%2B61%2Bmp%2Caps%2C67&sr=8-2&th=1)* VIDEO: [It could be really hot...](https://www.youtube.com/watch?v=BSGcnRanYMM&feature=related)* INFO: How many processors does [iPhone 14](https://www.apple.com/iphone-14/specs/) have?* INFO: What are the [top 500](https://www.top500.org/) Supercomputers?* INFO: The [OpenMP](http://www.openmp.org/) specification for parallel programming* INFO: What does [TPL](http://msdn.microsoft.com/en-us/library/dd460717.aspx)(Task Parallel Library) provide?* INFO: An example of using Intel's [TBB](http://pages.cs.wisc.edu/~gibson/tbbTutorial.html) (Thread Building Blocks)...* INFO: History of the [nCube](http://www.cpushack.com/2013/11/01/ncube-and-the-rise-of-the-hypercubes/) Supercomputer* INFO: What about Intel Core [i9 14900K](https://www.intel.com/content/www/us/en/products/sku/236773/intel-core-i9-processor-14900k-36m-cache-up-to-6-00-ghz/specifications.html) processor?* INFO: Some technical details of the NASA [Pleiades](https://www.nas.nasa.gov/hecc/resources/pleiades.html) Supercomputer* TUTORIAL: A tutorial on [Chapel](https://chapel-lang.org/tutorials.html) language* READING: About the [von Neumann architecture](https://en.wikipedia.org/wiki/Von_Neumann_architecture)* READING: A gentle introduction to [Parallel Programming](http://en.wikipedia.org/wiki/Parallel_computing)* READING: A gentle introduction to [multicore programming](http://serc.carleton.edu/csinparallel/index.html) platforms.* READING: A light reading about the [Moore's law](https://en.wikipedia.org/wiki/Moore%27s_law)* READING: [Gordon Moore recently passed away at 94](https://www.nytimes.com/2023/03/24/obituaries/gordon-moore-dead.html?unlocked_article_code=hrgymR5ZbWV-6F2sqauTasSDJwMnedMxBWJBaDbGq4FLsgjo8AxJLur1HjKBtzH1F4I2d_5pxMX7wGkCsY64uBtUdmgnhPG7oHTGUKHeGdEQlnIneod9bffbJW3GeV2R3YbeRlnHy3uwuEtTjXLK9Mw1fK6ushpLJR--FDqr_j6wNAM5C_6WIQ6nlDZuCy6QeuWVyTVK2U-XmBAzbdUzQS88vX9jxRIHfpPJoAY5EKzVRvLh7hbC3QW0kXvufcTmtsLJrcieqF-vstch19WBuvgg9G2-POhIZsze9vXhqz9hAr1g4cc4hj9y4IIAt-EXMl-ptp2aF6zDVavDaR8&smid=url-share)* READING: What to know more about the [Amdahl law](https://en.wikipedia.org/wiki/Amdahl%27s_law)?* READING in Depth: [The exponential nature of Moore's law](notes/CS322/mooreCACM012017.pdf)* READING in Depth: [Moore's law is on its way out.](http://www.nature.com/news/the-chips-are-down-for-moore-s-law-1.19338)* READING in Depth: [The last sixty years in parallel programming](notes/CS322/SixtyYearsConcurrentComputing.pdf)* READING in Depth: [Cooperating sequential processes](notes/CS431/cooperatingSequentialProcess1968.pdf) by D. E. Dijkstra* VIDEO: [Computer Networks: The Heralds Of Resource Sharing (Arpanet, 1972)](https://www.youtube.com/watch?v=7tG7LZgOb-U)- Graphs and graph based algorithms: 1. [Basics:](notes/CS322/note22.pdf) Graph representation and basic graph algorithms * INFO: The [Prerequisite structure](http://turing.plymouth.edu/~zshen/courseCharts/CS-Course-Chart.pdf) of B.S. in Computer Science (Fall 2021)* READING: The whole story about [Konigsberg bridge problem](https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg)* READING: [Euler](https://en.wikipedia.org/wiki/Leonhard_Euler), the great mathematician and his accomplishment* READING: More about the [four color problem](https://en.wikipedia.org/wiki/Four_color_theorem)* READING in Depth: [How many groups of people who know each othger](notes/CS322/ramsey.pdf)?* INFO: [One way streets in Boston](https://collections.leventhalmap.org/search/commonwealth:3t947b84j)* READING: More on [topological sort](https://en.wikipedia.org/wiki/Topological_sorting)- [Minimum spanning trees](notes/CS322/note23.pdf) * INFO: More details about the [Prim's algorithm](https://en.wikipedia.org/wiki/Prim%27s_algorithm#:~:text=In%20computer%20science%2C%20Prim's%20algorithm,in%20the%20tree%20is%20minimized.)* INFO: More details about the [Kruskal's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)* INFO: Code [examples](http://blog.benoitvallon.com/data-structures-in-javascript/the-set-data-structure/) for the set structure* READING: On the data structure of [set](https://en.wikipedia.org/wiki/Set_(abstract_data_type))- [Shortest paths](notes/CS322/note24.pdf) * INFO: Want to get an [AAA TripTik](https://www.ace.aaa.com/travel/triptik-travel-planner.html)?* READING: More information on the [Bellman Ford algorigthm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)* READING: More about [Dijkstra's algorithm](http://repository.unikama.ac.id/1516/1/materi%201%20dijkstra.pdf)* READING: How about the [longest path problem](https://en.wikipedia.org/wiki/Longest_path_problem)?* READING: What are the [longest hiking trails](https://www.worldatlas.com/articles/longest-hiking-trails-in-the-united-states.html) in United States?* READING:About the [Steiner tree problem](https://en.wikipedia.org/wiki/Steiner_tree_problem)- [Maximum flow](notes/CS322/note26.pdf) * READING: More information on the [Maximum flow problem](https://en.wikipedia.org/wiki/Maximum_flow_problem)* READING: How to find the [biggest bottleneck path](https://www.quora.com/What-is-the-maximum-bottleneck-s-t-path-in-the-context-of-maximum-flow)?- Computational complexities: 1. [Problem complexity:](notes/CS322/note34-1.pdf) How hard is it? * READING: A little more about the [Hanoi Tower](https://en.wikipedia.org/wiki/Tower_of_Hanoi) problem* READING in Depth: What is, and what do we do, with [computational complexity](https://en.wikipedia.org/wiki/Computational_complexity_theory)?* READING: Contribution by [Juris Hartmanis (1928-2022)](notes/CS322/jurisACM102022.pdf)* INFO: How much does [Miata](https://www.mazdausa.com/vehicles/2021-mx-5-miata?semid=73734938332&providertag=MazdaSEM&servicetag=73734938332&k_keyword=miata&k_matchtype=e&gclid=CjwKCAjw7J6EBhBDEiwA5UUM2gWo_tlGGS0q93kJ1fAc3NSJZW5JkauMPQ9aSyWGmS9yXmpBoL9O2xoCESUQAvD_BwE&gclsrc=aw.ds) really cost?- [NP-completeness:](notes/CS322/note34-2.pdf) The hardest of all * READING: A good introduction to the [traveling salesman](http://www.math.uwaterloo.ca/tsp/) problem.* READING: Dig more out of the [Hamiltonian cycle](https://en.wikipedia.org/wiki/Hamiltonian_path) problem* READING: More about the [Knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem)* READING: More about the [SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) problem* READING: What is this [P vs NP](https://en.wikipedia.org/wiki/P_versus_NP_problem) stuff?* READING: [Turing, his life, and his machine](https://www.newyorker.com/culture/culture-desk/living-in-alan-turings-future)* INFO: It is a [million dollar question](http://en.wikipedia.org/wiki/Millennium_Prize_Problems). - Why Algorithms?
The grade that a student receives for this course is calculated as the sum of the following components.
- Homework as given in the lecture notes: (25%)- Tests: (20%)
-
First test on Part 2 (Basics of Algorithm Analysis) and Part 3 (Faster sorting algorithms) .* Second test on Part 4 (Data Structures) and Part 5 (Algorithm design techniques) .- Projects: (20%)
To be fair to everyone in the class, no program submitted in this course may contain any complier error and/or warning message. Otherwise, the grade for that program will be a 0.
- A final Examination (35%) with a focus on Part 6 (Parallel programming fundamentals), Part 7 (Graphs and graph based algorithms, including trees), and Part 8 (Computational complexities): from 11 a.m. to 1:30 p.m., Monday, May 6, 2024
-
A calculated grade will then be converted to a letter grade by the following procedure: If a student gets at least 92.5, s/he will get 'A', if s/he gets between 87.5, and 92.4, s/he gets 'A-', so on and so forth, until s/he gets a grade below 42.5, when s/he will get 'F'.
To correct any unintentional inconsistency during the grading process, if your grade is within 0.5 of a letter grade, you will get that higher grade. Thus, e.g., if your final grade is at least 92.0, you will get A, instead of A-.
Your final grade for this course can be found here.