CSIS 430 Analysis of Algorithms


Picture of the Konigsberg bridges in the year 1581

Course Description

An introduction to the formal design and analysis of algorithms in terms of both time and space complexity. Paradigms covered include divide-and-conquer, greedy, dynamic programming, and heuristic techniques.


Instructor

J. Walker Orr, Ph.D.
Office hours: WMR 221 (see schedule)


Texts

required
recommended


Resources


Objectives

This course moves beyond the study of data structures to study and analyze efficient algorithms and paradigms for their design.


Course Organization

This course will emphasize both theory and practice. Algorithms studied through lecture and reading will be implemented in a high-level language. Experimental results will be compared with predicted theoretical results.

Programming assignments will be carried out in a prescribed high-level language. Minimal instruction in the use of this language will be provided, you will be expected to achieve sufficient competence on your own.

The course will include regular homework and programming assignments. All assignments will be graded on a pass/fail basis. If an assignment is "failed" it can be corrected and resubmitted as many times until it is "passed".

A first attempt for an assignment must be completed before the due date for it to be eligible for a "pass" or resubmission.

Reading assignments should be completed before the lecture covering the material. Not all reading material will be covered in the lectures, but you will be responsible for the material on homework and exams. Quizzes over the assigned reading may be given at any time.

The course will include regular homework and/or programming assignments. Unless otherwise specified, assignments are due 5 minutes before midnight on the due date. There will be no credit given for late assignments (without an excused absence)—turn in as much as you can.

Reading assignments should be completed before the lecture covering the material. Not all reading material will be covered in the lectures, but you will be responsible for the material on homework and exams. Quizzes over the assigned reading may be given at any time.


Collaboration

See the GFU CS/IS/Cyber policies for collaboration and discussion of collaboration and academic integrity. Most students would be surprised at how easy it is to detect collaboration in programming—please do not test us! Remember: you always have willing and legal collaborators in the faculty.

Almost all of life is filled with collaboration (i.e., people working together). Yet in our academic system, we artificially limit collaboration. These limits are designed to force you to learn fundamental principles and build specific skills. It is very artificial but intensional for your own benefit. The only way for you to learn is by doing the work.

To be clear, do not:


Engineering Your Soul

The mission and vision statement of the Computer Science & Information Systems (CSIS) program states that our students are distinctive by "bringing a Christ-centered worldview to our increasingly technological world."

As one step towards the fulfillment of this objective, each semester, the engineering faculty will collectively identify an influential Christian writing to be read and reflected upon by all engineering faculty and students throughout the term. As part of the College of Engineering, CSIS students participate in this effort, known as Engineering Your Soul (EYS). This exercise will be treated as an official component of every engineering course (including CSIS courses) and will be uniquely integrated and assessed at my discretion, typically as a component of the quiz grade.

Students have three options for satisfying the EYS requirement.

The deadline for all of these options is the Wednesday the week after the group meetings.

All the reflections should be posted to the canvas EYS course. A reflection should be 100 or more words and should consist of your personal thoughts on the book and/or meeting, not simply a summary of the book.


University Resources

If you have specific physical, psychiatric, or learning disabilities and require accommodations, please contact the Disability Services Office as early as possible so that your learning needs can be appropriately met. For more information, go to ds.georgefox.edu or contact Rick Muthiah, Director of Learning Support Services (503-554-2314 or rmuthiah@georgefox.edu).

The Academic Resource Center (ARC) on the Newberg campus provides all students with free writing consultation, academic coaching, and learning strategies (e.g., techniques to improve reading, note-taking, study, time management). The ARC, located in the Murdock Learning Resource Center (library), is open from 1:00–10:00 p.m., Monday through Thursday, and 12:00–4:00 p.m. on Friday. To schedule an appointment, go to the online schedule at arcschedule.georgefox.edu, call 503-554-2327, email the_arc@georgefox.edu, or stop by the ARC. Visit arc.georgefox.edu for information about ARC Consultants' areas of study, instructions for scheduling an appointment, learning tips, and a list of other tutoring options on campus.


Anonymous Feedback

At any point in the term, you can leave anonymous feedback via this form. If there is something you want or need to tell me about the course feel free to leave a comment.


Spiritual Formation

Besides EYS, I am always available to discuss the Christian faith if you have any questions or doubts. Send me an email, come by my office hours, or talk to my after class, Christ is the reason I am at GFU, I always have time to talk about faith.


Grading

The final course grade will be based on:

Grade Programming (7) Analysis (7) Zybooks (13) Participation
A 7 7 13 90%
B 6 6 12 80%
C 5 5 11 70%
D 4 4 10 60%

Each assignment is graded on a pass/fail basis. Failed assignments may be corrected and resubmitted, but the first attempt must be by the due date. Each assignment will be have the opportunity to be regraded once per day. The number of assignments you pass in each category determine your final grade. Your grade for the course will be the highest row you complete all the requirements for.

For the midterm and the final, your base grade may then be modified by your performance on each exam, as follows:

The modification from the midterm and final will be added together to produce the final modification. For example a step up and a step down cancel each other out. Also, two steps do add up to (almost) a full letter grade improvement, e.g. B to A-.


Tentative Schedule

Week 1

Introduction & Scala

Reading: Zybooks Chp. 1

Week 2

Running Time and Divide & Conquer

Reading: Zybooks Chp. 2

Week 3

Sorting

Reading: Zybooks Chp. 3 & 4

Week 4

Graphs & Shortest Path

Reading: Zybooks Chp. 5 & 6     Dijkstra Proof

Week 5

MST & Network Flow

Reading: Zybooks Chp. 7 & 8
Network Flow Video

Week 6

More Greedy Algorithms

Reading: Zybooks Chp. 9

Week 7

Introduction to NP

Reading: Zybooks Chp. 10

3/5

Midterm

Week 8 — 9

Dynamic Programming

Reading: Zybooks Chp. 11
0-1 Knapsack Video
Held-Karp TSP Video
Held-Karp TSP "Rewind" Clarification

Week 10

Randomized Algorithms

Reading: Zybooks Chp. 12
Intro. & primality testing.
Genetic Algorithm for the TSP video
Genetic TSP PDF

Week 11

Backtracking Algorithms

Reading: Zybooks Chp. 13
Intro. to Backtracking with N-Queens
Branch & Bound

Week 12

Spring Breakno class

Week 13

Backtracking Algorithms & Logic

ReadingTSP Backtracking
PDF
Intro. to Logic Video
Conjunctive Normal Form (CNF) and Satisfiability (SAT) Video

Week 14

Encryption

Reading: Zybooks Chp. 14
Intro. to Cryptography
PDF

Week 15

Special Topics

ReadingCS Theory, History, and Related Philosophy Video


This page was last modified on 2024-02-26 at 22:19:02.

Copyright © 2018–2024 George Fox University. All rights reserved.