CS 315 COMPUTER SCIENCE 315 Juniata College Algorithms and Analysis Spring 2021 Important Annoucement Regarding Remote Learning and Recording): Video and audio recordings of class lectures will be part of the classroom activity. The video and audio recording is used for educational use/purposes and may be made available to all students presently enrolled in the class. For purposes where the recordings will be used in future class session/lectures, any type of identifying information will be adequately removed from the videos. Due to Pennsylvanias Wiretap Law, we will be recording class sessions. By joining each class session, you consent to being recorded. More information about Pennsylvanias Wiretap Law is available at Recording Phone Calls and Conversations. Description: The study and analysis of algorithms, their complexity and supporting data structures. Topics include searching, sorting, mathematical algorithms, tree and graph algorithms, the classes of P and NP, NP-complete and intractable problems, and parallel algorithms. This course has a CW designation as a writing course. Prerequisites: CS 240 and MA 116 (or MA 210) Class Times and Locations: M W F 10:30 AM 11:40 AM Good 222 Instructor: Dr. Gerald Kruse Phone: 814-641-3595 Office: C-205A Brumbaugh Academic Center (BAC) E-mail: kruse@juniata.edu Office Hours: For the most up-to-date, see Office Hours To make a definite appointment, you may schedule (must be 2 hours in advance), via Calendly: https://calendly.com/dr-gerald-kruse . The default in Calendly is to meet via Zoom, but please email me, kruse@juniata.edu, if you would like to meet in person. CS Help Sessions: Textbook: Introduction to Algorithms, 3rd Edition, by Cormen et. al., , ISBN-13: 978-0262033848 Grading (Dates tentative): Exam 01, 100 pts. Mon, 11.Oct Exam 02, 100 pts. Wed, 08.Dec Writing Assignments, approx 400 pts. (50% of each writing assignment grade will be devoted to the quality of writing, with the opportunity for re-writes) Homework Assignments, approx 150 pts. (50% of each homework assignment grade will be devoted to the quality of writing) Class Attendance, Conduct, and Professionalism 25 pts. Expectations for Class Attendance: You are expected to engage with/access each scheduled class session. Students meeting in-person (eligibilty as determined by the Dean of Students Office) will follow the current safety guidelines put forth by Juniata College. Students meeting asynchronously will be expected to following the homework deadlines AND set up an appointment (via Calendly, https://calendly.com/dr-gerald-kruse) each week with the instructor, to review their progress, any questions, etc. This course is for everyone. Every student in this class should feel welcome to attend and participate freely. There is no tolerance in this class for discrimination based on race, ethnicity, gender, sexuality, disability, age, socioeconomic status, or culture. Remote Learning and Recording: Video and audio recordings of class lectures will be part of the classroom activity. The video and audio recording is used for educational use/purposes and may be made available to all students presently enrolled in the class. For purposes where the recordings will be used in future class session/lectures, any type of identifying information will be adequately removed from the videos. Due to Pennsylvanias Wiretap Law, we will be recording class sessions. By joining each class session, you consent to being recorded. More information about Pennsylvanias Wiretap Law is available at http://www.dmlp.org/legal-guide/recording-phone-calls-and-conversations Homework: 0- type your solution using a word-processing package, using an equation editor when appropriate (please, no handwritten scans) 1- clearly label each problem number and give an explanation for your solution 2- show your work and/or copy & paste your associated code, Maple worksheet, Excel spreadsheet, etc. Assignments and due dates available in Moodle. Style Manual: - The Pocket Wadsworth Handbook, 4th ed, by Kirszner and Mandell, Wadsworth Cengage Learning, 2008. Writing Assignments: A significant portion of the "4th" hour lab time will be devoted to writing. Suggestions on writing and style will be discussed when writing projects are assigned, and students will be met with individually when assignments are returned so feedback on writing can be provided. Comments will be provided on the writing in the draft, and a grade will be assigned for this writing component of the project. Each team/individual will be given feedback on their writing. Each team/individual will then have the opportunity to improve their writing and resubmit it, a little more than one week later. Each team will be met with again for feedback on the writing when returning the grade on the final draft. Assignments and due dates available in Moodle. Psuedocode: Insertion, Selection, and Mergesort from the Textrbook, Heap Psuedocode, Sorts.java, Matrix Matrix Multiply in C++, Optimization in C++, Ratio Test for Mat-Mat Multiply, quicksort.txt, Quicksort and Partition Psuedocode, AlgCheck.java, Partition Worksheet, Partition Example, CountingSort Psuedocode, Binary-Search Tree Psuedocode, R-B Tree Properties, R-B Tree Psuedocode, LCS Psuedocode, KMP Matching Algorithm, Open MP Example in C++ Bias in Algorithms: https://www.nytimes.com/2020/06/24/technology/facial-recognition-arrest.html?utm_source=pocket&utm_medium=email&utm_campaign=pockethits https://blog.getpocket.com/2020/06/the-bias-embedded-in-algorithms/?utm_source=pocket&utm_medium=email&utm_campaign=pockethits Code and Server Instructions: Dr. Java, IT CS Server via eXtend and PuTTY,Timing in Java and C++, Running Visual C++, Excel Tips, Ratio Test Example Additional links: Sample SVD SVD and the Netflix Challenge Caesar Cipher hints RSA (and Caesar Cipher) hints for Maple Hollerith Card Example BLAST in Wikipedia BLAST Explained Representations Divide by 70 log approximation Induction Proof Results Blank Inductive Proofs Detailed Sample Proof Are Automated Algorithms Biased? Distributed Memory Fan-In Google's Ranking Changes An Interesting Discussion of Euler's Sums Sum of the squares of inverses Running of the Squirrels Herding Cats Bambi Meets Godzilla The Longest Path Triominoes R-B Tree Visualization Google Corn Mazes Corn Maze Solution Writing Tips Breaking the Code to Find Hidden Treasure? Fighting Bias in Algorithms Terrible mishap with algorithms Content: Growth of Functions / Summations, Recurrence Relations, O( ) sorts, Heapsort, Quicksort, other O( ) sorts, sorting in linear time, Medians and Order Statistics, Hash Tables, Binary Search Trees, Red-Black Trees, Augmenting Data Structures, Elementary Graph Algorithms, Pattern Matching, Internet Algorithms, NP-Completeness Sorting Animations The home of Zestful Algorithms. John F. Stuntgoat Standard Course Policies: For the most up-to-date, see http://jcsites.juniata.edu/faculty/kruse/policies.htm
