CS601 Algorithms, Architecture, and Languages (Proposed Course)

Course
99999
Section
F01
Credits
4 + 0
Prerequisites:
  • CS331
  • CS411
  • CS441 or EE443
Instructor
Orion Lawlor
Phone
907-474-7678
Office
Duckering 529
Email
lawlor@alaska.edu
Office Hours
By Appointment
Meeting Time
Room
Chapman 104
Course Website
/courses/cs601-algorithms-architecture-and-languages/cs601/2015-spring/
Required Texts
(NTO) The New Turing Omnibus: Sixty-Six Excursions in Computer Science, by A. K. Dewdney

Course Description

Current research on, and cross-cutting interrelationships between computer algorithms, machine architecture, and languages. Covers asymptotic performance analysis including NP-completeness, modern parallel hardware including multicore, and grammars and parsing from regular expressions to BNF.

Tentative Schedule

    • First day of instruction
      • Volunteer for lecture topics through spring break
    • Alaska Civil Rights Day (no classes, most offices closed)
    • Godel's incompleteness theorem & computability (NTO 5)
    • Turing machines, and the halting problem (NTO 59)
    • Noncomputable functions: busy beaver (NTO 39)
    • Physical models for computation (NTO 33)
      • Homework: Turing Machines
    • Turing machine simulation (NTO 31) & virtualization
    • Chomsky hierarchy of languages (NTO 7)
    • Pumping lemma (NTO 14) & non-regular languages
    • Deadline for student- and faculty-initiated drops (course does not appear on academic record)
    • Regular languages, and regular expression syntax
      • Homework: lexer design
    • Lexer design in compilers
    • String substitutions and halting (NTO 63)
    • PROJECT: Preliminary proposals for semester projects
    • Nondeterminism: NFA to DFA (NTO 26)
      • Homework: YACC
    • Context Free Grammars, parsing, and compiler design
    • Bottom-up and shift-reduce parsing, LALR
    • YACC and BNF: LALR in practice
    • Deadline to apply for spring 2015 graduation
    • Introduction to graph data structures & algorithms
      • Homework: graph library
    • Review: Prim's greedy minimum spanning tree (NTO 22)
    • Traveling Salesman Problem, with application to 3D printer path planning
    • Satisfiability and graph coloring (NTO 34)
    • Boolean normal forms & circuits (NTO 13), with application to ASIC design
      • Homework: P vs NP
    • NP Completeness and SAT (NTO 41)
    • Proving NP-Completeness (NTO 54)
    • Dynamic programming: filling in tables (NTO 601), with application to DNA sequencing
    • Random and pseudorandom numbers (NTO 8)
      • Homework: Monte Carlo
    • Monte Carlo integration, with application to financial modeling
    • Probabilistic Algorithms: Rabin prime finding (NTO 50), with application to RSA encryption
    • Approximate solutions to NP-hard problems
    • Multi-precision arithmetic, with application to encryption on prime groups
      • Homework: RSA
    • Number systems and base conversion, Chinese remainder theorem (NTO 42)
    • Rivest-Shamir-Adleman (RSA) public key encryption
    • PROJECT: Prior work reports
    • Deadline for student- and faculty-initiated withdrawals (W grade appears on academic transcript)
    • Spring break begins (no classes)
    • Spring break--most offices closed
    • Physical machines and silicon (NTO 56), with application to chip fabrication
      • Volunteer for lecture topics through final exam
    • Triumph of the MOSFET, and quantum effects on modern silicon
    • Shor factoring on quantum computers
    • Adiabatic quantum machines and annealing
    • Parallel computing machine topologies (NTO 62)
      • Homework: OpenMP + AVX
    • Multicore, atomics, and locks
    • SIMD: regular parallelism, with application to high-speed decryption
    • Mixing SIMD and Multicore memory access
    • GPU programming: fragment shaders
      • Homework: GPU
    • GPU programming: CUDA
    • Rendering the mandelbrot set per pixel (NTO 9)
    • Cellular Automata: Conway's game of life (NTO 44)
    • Floating point representation and roundoff
      • Homework: floating point
    • Newton-Raphson root finding and convergence (NTO 21)
    • Multi-precision floating point arithmetic, and Dekker addition
    • Fast Multiplication: Karatsuba & Strassen (NTO 25)
    • Genetic algorithms and crossover-friendly genomes (NTO 19)
      • Homework: neural networks
    • Neural Network topology & training (NTO 36)
    • Data compression via Huffman trees (NTO 52)
    • Reed-Solomon error correcting codes
    • SpringFest (no classes)
    • Comprehensive exam after-action (part 1)
    • Comprehensive exam after-action (part 2)
    • PROJECT: Final presentations
    • PROJECT: Final presentations cont'd
    • Last day of instruction
    • PROJECT: Final presentations cont'd
    • Final exam, held in class

Grading Policies

Weight Description
10% Attendance and participation in daily class discussions
15% In-class lecture preparation and delivery
20% Homeworks and technical writeups of course material presented in class
25% Semester project: a written proposal, experimental work, writeup, and a presentation.
30% Final exam: a comprehensive written exam.

Grades will be assigned based on the following percentage intervals:

A+
[99%, 100%)

A
[93%, 99%)
A-
[90%, 93%)
B+
[87%, 90%)

B
[83%, 87%)
B-
[80%, 83%)
C+
[77%, 80%)

C
[70%, 77%)
C-
[70%, 70%)
D+
[67%, 70%)

D
[63%, 67%)
D-
[60%, 63%)
F
[0%, 60%)

Course Format

Each day of class will begin with a half hour lecture, surveying and describing the course material.  The second half hour of each class will be a moderated discussion between the presenter, instructor, other students in the course, and invited guests.

To prepare an effective lecture, you must not only read the starter source material provided by the instructor, but also find, read, and evaluate other scholarly sources, for example via Google Scholar.  Lecture grades will be based on your written lecture outline submitted to the instructor before class; the quality of your slides, diagrams, videos, or other visual aids during the presentation; your ability to engage the audience; and your demonstrated depth and clarity of understanding of the subject and how it relates to the broader field.

  • A grade "A" lecturer works to find and understand related papers, finds and focuses on the key areas, spends significant effort on interactive examples and demonstrations, practices their talk, and presents the material clearly and in context.
  • A grade "B" lecturer finds a few related papers and some tangential ones, agglomerates them into a powerpoint with text and figures, and delivers a rambling and still incomplete talk.
  • A grade "C" lecturer reads the book, prepares text-only powerpoint slides, reads them, and puts the audience to sleep.

To be prepared for the in-class discussion each day, you must at a minimum read the lecture notes, and the related book chapter and/or technical papers.  Discussion grades will be based on attendance, the quality of questions asked, and your demonstrated engagement with both the subject and discussion. The use of laptops or tablets during the lecture to take notes, run experiments, and seek out related scholarly information is highly encouraged, but their use to check email or write unrelated code is not. 

Our emphasis on clear written and oral communication skills is not to the exclusion of technical work, but due to the fact that employment, funding, and recognition all require both technical and communication skills!

Student Learning Outcomes

Students finishing this course will be able to:

  • Explain how to determine if a problem is NP-Complete.
  • Explain limits on computability, such as the busy beaver problem.
  • Explain LALR parser generation, such as in a YACC parser.
  • Design and construct parallel programs using at least one of multicore, SIMD, or GPU.
  • Read and write technical literature, such as program documentation, white papers, and academic journal articles.

Policies

Students are expected to be at every class meeting on time, and are responsible for all class content, whether present or not. If absence from class is necessary, in-class work (other than quizzes) and homework may be made up only if the instructor is notified as soon as possible; in particular, absences due to scheduled events must be arranged ahead of time. Academic dishonesty will not be tolerated, and will be dealt with according to UAF procedures. Students in this class must pay the CS lab fee.

UAF academic policies http://www.uaf.edu/catalog/current/academics

CS Department policies http://www.cs.uaf.edu/departmental-policies/

Disabilities Services:

The UAF Office of Disability Services implements the Americans with Disabilities Act (ADA), and ensures that UAF students have equal access to the campus and course materials. I will work with the UAF Office of Disability Services (208 WHITAKER BLDG, 474-5655) to provide reasonable accommodation to students with disabilities.

Updated: