Graduate Information

CUNY’s top computer and information science department will position you to lead this continually evolving and dynamic field. What better way is there to continue your computer and information science studies than through the Brooklyn College Computer and Information Science Department? We lead the City University of New York, as well as many other universities and colleges nationwide, in cutting-edge resources for teaching you all the latest and most advanced CIS systems, programs, applications, and theories. Our faculty experts are leaders who stand at the forefront of the digital-world curve. Your graduate degree will be well respected by individuals and organizations in the wide range of CIS–related industries across the nation and will enable you to secure rewarding positions at all levels or to advance your current career. The department is also an active participant in the PIMA-M.F.A. program.

Programs

Program Finder

Courses

Course Finder

Additional Resources

Advice to Graduate Students

Advice Brochure 2020

Schedule for Graduate Courses

Three-Year Schedule for Graduate Course Offerings

The three-year course offering is subject to change, depending on enrollment and staffing.

2021–22

Fall Semester Spring Semester
CISC 7120X Programming Languages and Compilers
CISC 7200X Analysis of Algorithms
CISC 7300X Computer Systems and Architecture
CISC 7410X Artificial Intelligence
CISC 7450X Computer Applications in Health Sciences
CISC 7500X Introduction to Management Information Systems
CISC 7510X Database Systems
CISC 7534X Information Systems Planning and Policy
CISC 7540X Software Methodology
CISC 7700X Introduction to Data Science		 CISC 7124X Object-Oriented Programming
CISC 7221X Theoretical Computer Science
CISC 7302X Computer Architecture
CISC 7310X Operating Systems I
CISC 7330X Teleprocessing SystemsCISC 7512X Advanced Database Systems
CISC 7520X Requirements Modeling for Information Systems
CISC 7522X Systems Analysis and Design
CISC 7530X IT Project Management

2022–23

Fall Semester Spring Semester
CISC 7120X Programming Languages and Compilers
CISC 7200X Analysis of Algorithms
CISC 7410 Artificial Intelligence
CISC 7450X Computer Applications in Health Sciences
CISC 7500X Introduction to Management Information Systems
CISC 7510X Database Systems
CISC 7530X IT Project Management
CISC 7540X Software Methodology
CISC 7700X Introduction to Data Science		 CISC 7124X Object-Oriented Programming
CISC 7221X Theoretical Computer Science
CISC 7302X Computer Architecture
CISC 7310X Operating Systems I
CISC 7332X Local Area Networks
CISC *7440X Pattern Recognition and Neural Networks
CISC 7512X Advanced Database Systems
CISC 7520X Requirements Modeling for Information Systems
CISC 7534X Information Systems Planning and Policy

2023–24

Fall Semester Spring Semester
CISC 7120X Programming Languages and Compilers
CISC 7200X Analysis of Algorithms
CISC 7312 Operating Systems II
CISC 7450X Computer Applications in Health Sciences
CISC 7500X Introduction to Management Information Systems
CISC 7510X Database Systems
CISC 7530X IT Project Management
CISC 7540X Software Methodology
CISC 7700X Introduction to Data Science		 CISC 7124X Object-Oriented Programming
CISC 7221X Theoretical Computer Science
CISC 7214 Algorithms and Complexity
CISC 7302X Computer Architecture
CISC 7310X Operating Systems I
CISC 7330X Teleprocessing Systems
CISC 7520X Requirements Modeling for Information Systems
CISC 7512X Advanced Database Systems
CISC 7534X Information Systems Planning and Policy

2024–25

Fall Semester Spring Semester
CISC 7120X Programming Languages and Compilers
CISC 7200X Analysis of Algorithms
CISC 7140X Artificial Intelligence
CISC 7450X Computer Applications in Health Sciences
CISC 7500X Introduction to Management Information Systems
CISC 7510X Database Systems
CISC 7530X IT Project Management
CISC 7540X Software Methodology
CISC 7700X Introduction to Data Science		 CISC 7124X Object-Oriented Programming
CISC 7221X Theoretical Computer Science
CISC 7302X Computer Architecture
CISC 7310X Operating Systems I
CISC 7332X Local Area Networks
CISC 7520X Requirements Modeling for Information Systems
CISC 7512X Advanced Database Systems
CISC 7522X Systems Analysis and Design
CISC 7534X Information Systems Planning and Policy

Guidelines for Master’s Thesis Proposals

  1. The student must have a GPA of 3.50 or above.
  2. The student needs to find an adviser who will mentor him or her for the thesis research.
  3. With the adviser’s help, the student needs to write a research proposal that:
    • includes a statement of the goal of the research,
    • gives a short background of the research area with citations of relevant research,
    • describes exactly what the student’s contribution will be,
    • describes the outcomes that are expected, and
    • includes a timeline for accomplishing the research.
  4. The student sends the proposal to the graduate deputy chair and the proposal is read by a committee of at least three faculty members that has been assembled by the adviser. Members of the thesis committee shall include a member of the Graduate Curriculum Committee and the thesis adviser. Once the proposal is approved, the student will be given permission to register for the thesis research course.
  5. It takes most students at least a year to perform the research and write the thesis.

FAQ

Applying

What are the requirements for the master’s program?

The M.S. Program in Computer Science with specializations in computation, information systems, and health informatics is 30 credits of graduate classes. Review the exact requirements.

The programs are designed for students who have a significant undergraduate education in computer science, but it is also possible for students without the required background to take the necessary undergraduate classes. These undergraduate classes are in addition to the requirements listed above.

What are the prerequisites for the master’s program?

For the M.A. Program in Computer Science, you need to have taken the following classes (Brooklyn College course numbers in brackets):

  • Introduction to Programming in Java (CISC 1115)
  • Discrete Structures (CISC 2210)
  • Advanced Programming Techniques (CISC 3115)
  • Data Structures (CISC 3130)
  • Computer Architecture (CISC 3310)
  • Calculus I (MATH 1201)

For the M.S. Program in Information Systems, you need to have taken the following classes (Brooklyn College course numbers in brackets):

  • Introduction to Programming in Java (CISC 1115)
  • Discrete Structures (CISC 2210)
  • Advanced Programming Techniques (CISC 3115)
  • Data Structures (CISC 3130)
  • Computer Architecture (CISC 3310)
  • Calculus I (MATH 1201)
  • Probability and Statistics (MATH 2501)

For the M.S. Program in Health Informatics, you need to have taken the following classes (Brooklyn College course numbers in brackets):

  • Introduction to Programming in Java (CISC 1115)
  • Discrete Structures (CISC 2210)
  • Advanced Programming Techniques (CISC 3115)
  • Data Structures (CISC 3130)
  • Additionally, you must have taken 18 credits in health-related classes (health, biology, kinesiology, etc.).

College rules prevent you from needing more than two of these when you are admitted as a matriculated graduate student.

Can I apply to the program without having completed all the prerequisites?

Yes. You can be accepted as a matriculated master’s student if you have only two or fewer of the prerequisite courses remaining to complete. If you need to complete more than two prerequisite courses, then Brooklyn College rules prevent you from being admitted as a matriculated graduate student. However, you can apply and be accepted as a nondegree student, complete the prerequisite requirements, and apply to become matriculated in the master’s program.

How do I apply?

All the information you need to know about application is provided by the Graduate Admissions Office.

What is the deadline to submit my application?

The formal deadline is November 1 for spring admission and March 1 for fall admission, although we will accept applications that we receive soon after either deadline.

How can I transfer to Brooklyn College as a master’s student?

First, you need to apply to Brooklyn College and be accepted. If you are accepted into a program, we can look at your prior record to see if there are any courses that are equivalent to courses at Brooklyn College. Such courses can be transferred, up to a limit of three courses. Note that you cannot transfer credits that were used toward a previous degree. Also note that you cannot use undergraduate credits for a graduate degree.

Financial

What is the cost of attending Brooklyn College?

Review the current information on tuition and fees.

What financial assistance is there for master’s students?

In common with most master’s programs, the programs at Brooklyn College have very little financial support to offer incoming students. Once you are a student in the program, there are some scholarships available for master’s students at the college.

Classes

What are the start dates for the next semester?

The dates for the semester are published on the college calendar.

What classes are being offered next semester? When are classes scheduled next semester?

You can find this information on the college’s course schedules.

Which professors are teaching graduate classes next semester?

You can find this information on the college’s course schedules.

I have to take some undergraduate classes to complete the prerequisites for the program. Do I have to take these before I take graduate classes?

Yes. The course registration system will not allow a student to take graduate-level courses if the prerequisites have not been completed.

Department Chair

Yedidyah Langsam
P: 718.951.5000, ext. 2056

Consult Graduate Deputy Chair Professor James L. Cox for graduate program advice, 718.951.5000, ext. 2047

Application

Admissions Office

All Other Inquiries

E: cis@sci.brooklyn.cuny.edu

Course Syllabi

  • The syllabi shown below are intended to provide information about course content. Textbooks and weighting of grades are determined by the instructor of each section. See your instructor’s webpage for specific information.

Graduate Courses

Reading Lists for Comprehensive Exams

The examination is 3.5 hours long. You must answer three of the nine parts; you do not have to decide in advance which three parts you will answer. In the examination room, you will receive all parts of the exam, and you can make your decision at that time. However, it is strongly suggested that you plan to answer certain parts, with the option to change your mind after seeing all of the exams.

The rules are different for M.A. students and M.S. students.

  • M.A. students must take the Analysis of Algorithms examination, plus two other parts.
  • M.S. students must take the Management Information Systems examination, plus two other parts.

Grading

Each part of the examination is written by a separate committee and graded by that committee. In order to pass the Comprehensive examination, students must pass all three parts (this includes Analysis of Algorithms for M.A. students and Management Information Systems for M.S. students).

  • As of fall 2016, if you complete all the answers on three parts of the exam but pass only one part, you will have to retake the missing two parts.
  • If you fail one part and pass the other two, you will receive credit for those two parts. The next time you take the exam, you will have to pass only one part.

Brooklyn College policy allows graduate students to attempt to pass the exam two times.

Examination Format

The Master’s Comprehensive Examination has nine parts, one of which is further divided into subparts.

The nine parts are:

(M.A. students must take this exam)

A. Discrete Structures

  • Induction and Recursion
  • Propositional Logic, Boolean Algebras
  • Set Operations
  • Properties of relations, Closures, Properties of Functions
  • Countable and Uncountable Sets, Diagonalization
  • Combinatorics
  • Alphabets, Strings, Languages

B. Data Structures

  • Linked Lists, Stacks, Queues, Graphs, Trees, Terminology and Representation
  • Tree Traversal (Inorder, Preorder, Postorder) and Graph Searching (Depth first, Breadth first)
  • Sorting: Insertion, Bubble, Quick, Heap, Merge, Bucket
  • Binary Search Trees, 8-Trees, Heaps

C. Analysis of Algorithms and Algorithmic Strategies

  • Big-O Omega and Theta notations
  • Upper Bound (e.g., Analysis of Heapsort) and Lower Bound For Sorting with Comparisons
  • Union-Find Algorithm
  • Divide and Conquer Strategy and Solving Recurrence Relations: e.g. Analysis of Merge sort, Quick-sort, K-th Selection Strassen’ s Matrix Multiplication
  • Greedy Strategy e.g. Minimum Spanning Tree (Prim, Kruskal). Shortest Path (Dijkstra)
  • Dynamic Programming: e.g., All Pairs Shortest Paths, Discrete (0-1) Knapsack, Traveling Salesperson
  • Backtracking: e.g., 8-Queens, Graph Coloring

D. Computational Complexity

  • Background knowledge about Turing Machines and the Unsolvability of the Halting Problem
  • Computational Complexity: Time and Space, P, NP, PSPACE
  • The Concept of Problem Reduction, NP-Completeness, Satisfiability and Cook’s Theorem
  • Other NP-Complete Problems: e.g., Traveling Salesperson, Hamiltonian Circuit, Vertex Cover, Clique, Discrete Knapsack

Textbooks

A. Binary Representations of Data

  • Binary Representations of Octal, Decimal and Hexadecimal digits
  • Binary Representation of Characters, ASCII code
  • Representations of Signed and Unsigned Integers and Fractions
  • Packed Decimal, 2’s Complement and Signed Magnitude
  • Representations of Fixed Point and Floating Point numbers
  • IEEE Floating Point format

B. Design of Combinational functions and circuits

  • Boolean Algebra, Truth Tables and Karnaugh Maps
  • Gates, Combinational circuits, and timing delays
  • Decoders, Multiplexers, Full and Half Adders, Full and Half Subtractors, Combinational Multiplier and Divider Circuits, and Logic Circuits, ROMs and PLAs

C. Design of Sequential functions and circuits

  • State Diagrams, State Tables and Register Transfer Language Programs
  • Flip-flops, Registers; the Clock and Timing Control
  • Registers with various operations such as: Counters, Logical and Arithmetic Shift operations, and Parallel Load operations.
  • Integer and Floating Point .Sequential Multiplier and Divider circuits

D. Register Transfer Language (RTL)

  • Representation of Control functions and Microoperations
  • Specification of Register and Memory transfers, Buses, Arithmetic and Logical operations
  • Translation of an RTL program into a Logic Diagram
  • Timing Signals and Control Signals

E. Performance and Cost Analysis

  • Benchmarks, Performance Measures, Performance and Execution Time, Amdahl’s law, Speedup, CPU Time, Clock Cycle Time and Clock Rate, Cycles per Instruction and Instruction Count

F. Instruction Set Principles

  • Accumulator, Stack and General Purpose Architectures
  • Register-Register (or Load-Store Architecture) and Register-Memory Architectures
  • Operand Addressing Modes, Instruction Set Operations, Type and Size of Operands and the Encoding of an Instruction Set
  • RISC versus CISC

G. Design and Performance Analysis of a non-Pipelined CPU

  • An RTL Program Specifying the Fetching and Execution of Instructions
  • Operand Address Decoding
  • Interrupt Cycle
  • Hard-Wired and Microprogrammed Control Units
  • Microprogram Instructions and Formats
  • Control Words

H. Design and Performance Analysis of a Pipelined CPU

  • Relationship between an Instruction set and a Pipelined CPU
  • Pipeline Registers
  • Pipeline Data and Control Hazards
  • Stalls
  • Forwarding
  • Instruction Scheduling, Delay Slots and a Delayed Branch
  • Multi-cycle Operations and Exception Handling

I. Memory-Hierarchy Design and Performance Analysis

  • Principle of Locality
  • Cache, Main Memory and Secondary Memory
  • Cache hit rate and time, miss rate and time, and miss penalty
  • Direct, Associative, and Set Associative mappings
  • Replacement Algorithms
  • Write Through and Write back Caches
  • Main Memory, the CPU-Memory Bus, Access time and Cycle time, and bandwidth
  • Design of 1-Dimensional and 2-Dimensional RAMs and DRAMs
  • Interleaved Memory and Memory Banks
  • Virtual Memory

J. I/O and Storage System Design, and Performance Analysis

  • Magnetic Disks
  • I/O Buses, Bus Masters and Synchronous and Asynchronous Buses
  • Data Transfers. Hand Shaking, Cycle Stealing, Bus Request and Acknowledge
  • I/O programming and Interrupt Handling
  • DMA and 10P
  • I/O Performance Measures

K. Multiprocessors

Textbooks

  • J. Hennessy & D. Patterson, Computer Architecture A Quantitative Approach, 2nd Edition, Morgan Kaufmann.
  • J. Hayes, Computer Architecture, 2nd Edition, Hayes, McGraw-Hill.
  • M.M. Mano, Computer System Architecture, 3rd Edition, Prentice Hall.
  • D. Patterson and J. Hennessy, Computer Organization and Design, 3rd Edition, Morgan Kaufmann.

A. Search Techniques

  • Generate-and-Test approach
  • Constrain-and-generate approach
  • Uninformed search methods (depth-first, breadth-first, etc.)
  • Branch-and-bound
  • Informed search methods (best-first, beam, A*, etc.)
  • Heuristics for informed search methods and constraint satisfaction problems
  • Adversarial search techniques and games (Minimax, Alpha-Beta Pruning)

B. Knowledge Representation

  • Semantic networks
  • Frames
  • Production rule systems
  • Neural networks and genetic algorithms

C. Logic

  • Propositional Logic
  • First-order (predicate) logic
  • Clausal form (including skolemization)
  • Unification
  • Resolution

D. Applications

  • Expert systems
  • Learning
  • Constraints and propagation
  • Planning
  • Natural language processing

Textbooks

  • G. F. Luger and W. Stubblefield, Artificial Intelligence, Third Edition, Addison-Wesley, 1998.
  • S. Russell and P. Norvig, Artificial Intelligence – A Modern Approach (second edition), Prentice Hall, 2003.
  • P. H. Winston, Artificial Intelligence, Addison Wesley, 1992.
  • M. R. Genesereth and N. J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann 1987.
  • C. J. Hogger, Essentials of Logic Programming, Oxford UP 1990.
  • B. Coppin, Artificial Intelligence, Jones and Bartlett, 2004.

Note

Russell/Norvig is useful for areas A–D, but you may wish to consult Genesereth/Nilsson or Hogger to get more background on logic. Winston is very useful for all areas except logic.

  • Introduction to Database Systems
  • The Relational model, ER diagrams, Relational algebra
  • Database Design
  • Normal Forms
  • Study of Several Real-world Database Management Systems (DBMS’s)
  • SQL
  • Query and Transaction Processing
  • Concurrency, Recovery
  • Distributed, Parallel, Client-server, and Object-oriented Databases

Textbooks

  • Rob, Peter, et al. Database Systems, Cengage Learning, 2013.
  • Date Addison-Wesley, Introduction to Database Systems (Eighth Edition), 2003.
  • Korth, Silberschatz, Sudrashan, Database System Concepts (Fifth Edition), McGraw-Hill, 2005.
  • Ricardo, Jones and Bartlett, Databases Illuminated, 2004.

Note

Although some books may not cover all of the topics listed above, a good knowledge of any one of the books, plus material on individual DBMSs, should be sufficient to pass the exam.

(M.S. students must take this exam)

  • Requirements elicitation processes, functional requirements, non-functional requirements, requirements analysis techniques:
  • UML Diagrams—general definitions and creation of use-case model diagrams, activity diagrams, sequence diagrams, class diagrams, and state transition diagrams
  • Information Systems Planning—guidelines for effective planning, tools for identification of opportunities, innovating with technology, systems for strategic advantage, development processes for strategic, tactical and operational plans
  • Systems Analysis—approaches, phases, fact-finding techniques including sample size determination, feasibility tests, alternate design approaches, user interface design
  • Telecommunications—types of networks, transmission media, transmission speed, network protocols, network topologies, OSI Reference Model, wireless technologies
  • Testing techniques and software quality assurance—unit testing, regression testing, equivalence class partitioning, boundary value analysis, path analysis, integration testing, smoke testing, black box testing, white box testing, risk identification/management/amelioration
  • Methodologies, Strategies, and Tactics for Software Development and Implementation—waterfall (SDLC), prototyping, RAD, RUP, scrum, XP, agile, custom development options, purchased packages, user-developed software, combinations, conversion strategies from old to new systems, ASPs, six sigma, capability maturity model, outsourcing alternatives
  • Software Estimation Methods—lines of code, function point analysis, COCOMO, cyclomatic complexity
  • Project Adoption—project evaluation and prioritization techniques, risk identification/analysis (brainstorming, nominal group technique, Delphi method, etc.), justifying technology investments (Payback period, Break-even, Return on Investment, Net Present Value, Internal Rate of Return)
  • Organization structure types, organizing a framework for systems technology management
  • Changing nature of software, types of artificial intelligence, managerial support systems, decision support systems, executive information systems, GISs, E-commerce, enterprise-wide applications
  • Project Scheduling—quantitative and probabilistic—CPM and PERT calculations, types of buffers, resource leveling and smoothing, tradeoffs between methodologies
  • Information Systems Project Failure—major categories (Lyytinen/Hirschheim, etc.), primary reasons, impact and cost of defect removal by project phase (Boehm, etc.)
  • Project Control and Assessment—risk management categories, planning vs. control issues, cost/benefit and risk analyses, scope management, quality management, project closure

Exam Format

There will be a series of relatively short questions, with some choice. The exam may have a case study, but a case study may not be present each time the exam is given. If there is a case study, there will be several questions on it. For example, you might have to answer a total of 12 out of 15 questions including two case study questions.

Textbooks

  • Kenneth C. Laudon and Jane P. Laudon, Management Information Systems: Managing the Digital Firm, 15th edition. Pearson, 2018.
  • Joseph Valacich and Joey George, Modern Systems Analysis and Design, 8th edition. Pearson, 2017.
  • Jack T.Marchewka, Information Technology Project Management, 5th edition. John Wiley & Sons, 2015.
  • Roger S Pressman and Bruce R. Maxim, Software Engineering: A Practitioner’s Approach, 8th edition. McGraw Hill, 2015.

A. OS Types and Organization

  • Batch; multi-programming, time-sharing
  • Multiprocessor or multicore, distributed, client-server, clustered, real-time systems
  • Structure of OS—simple, layered, microkemel
  • Virtual Machines
  • Protection CPU, Memory, 1/0

B. Input-Output

  • Interrupt, trap, interrupt vector
  • Interrupt mechanism and handling, privileged instructions
  • Alternatives to interrupts: busy-waiting, polling
  • Buffering, OMA
  • I/O Processing

C. Process Management

  • Process concept and process scheduling
  • Serving process requests (synchronous and asynchronous interrupts)
  • Process switching mechanism
  • Cooperating processes, inter-process communication, sockets, RPCs
  • Multi-threading—types of threads, multi-threading models system calls, etc.

D. CPU Scheduling

  • Basic concepts
  • Interactive versus batch processing
  • Scheduling criteria and algorithms—First Come First Served, Shortest Job First, Priority, Round-Robin, Multi­level Queue, Multi-level Feedback Queue

E. Process Synchronization

  • Critical section problem, synchronization hardware and primitives, semaphores, monitors, mutex locks
  • Classical problems of synchronization: Bounded-Buffer, Producer-Consumer, Readers-Writers, Dining Philosophers

F. Deadlocks

  • Conditions, prevention, avoidance, detection, and recovery
  • Resource allocation graphs, Banker’s Algorithm

G. Memory Management

  • Logical versus physical memory
  • Memory management hardware
  • Memory allocation—MFP, MVP (best-fit, worst-fit, first-fit), internal and external fragmentation
  • Paging: page table organization, special hardware support, page table structure (hierarchical, hashed, inverted), shared pages
  • Segmentation: segmentation implementation, shared segments, segmentation with paging
  • Virtual memory:·demand paging, pre-paging, page replacement algorithms (FIFO, Optimal, LRU, Additional reference bits, Second Chance/Clock), allocation of frames, thrashing, working set theory and its application to paging, program structure.

H. Mass Storage Structure

  • File systems and their implementations
  • Magnetic disc hardware, seek time, rational latency
  • Other types of storage devices
  • Disk Scheduling Algorithms—First Come First Served, Shortest Seek Time First, SCAN, C-SCAN, LOOK, C-LOOK

Textbooks

  • Silberschatz & Galvin, Operating Systems Concepts, 6th edition, Addison-Wesley, 2003.
  • Tanenbaum, Modern Operating Systems, 2nd edition, Prentice-Hall, 2001.
  • Stallings, Operating Systems Internals and Design Principals, 4th edition, Prentice-Hall, 2001.

Compilers

  • regular expressions
  • finite automata
  • context-free grammar
  • recursive-descent parsing
  • storage organization
  • activation record
  • parameter passing
  • symbol table
  • dynamic storage allocation

OOP

  • state (instance variable, data members) I behavior (methods, member functions) of a class
  • class, instance/class variables
  • data access: public I private I protected
  • Inheritance (is-a) versus Composition (has-a)
  • upcasting, downcasting
  • message passing, receiver, this
  • constructors: default constructors
  • get/set methods
  • high-level versus low-level classes/methods
  • overloading/overriding
  • polymorphism
  • reading/writing objects for persistence
  • super/subclasses; super/subinterfaces
  • abstract classes and methods
  • OOP languages (Java and C++)

Functional Programming

  • types
  • pattern-matching
  • recursion
  • lambda expressions
  • polymorphism
  • higher-order functions
  • FP languages (Haskell and Python)

Textbooks

  • Aho A., Lam, M., Sethi, R., Ullman, J., Compilers: Principles, Techniques, & Tools, Addison Wesley, 2007.
  • Timothy Budd, An Introduction to Object-Oriented Programming, 3rd Edition, Addison Wesley, 2002.

Textbooks

  • Text #1: Stallings, William, Data and Computer Communications, 7th edition, Prentice-Hall.
  • Text #2: Kurose, James and Ross, Keith, Computer Networking, 2nd edition, Addison Wesley.

Readings

  • Text #1 Chapter 1: Data Communications and Networking Overview or Text #2 Chapter 1: Computer Networks and the Internet
  • Text #1 Chapter 2: Protocol Architecture or Text #2 Chapter 1: Computer Networks and the Internet
  • Text #1 Chapter 3: Data Transmission
  • Text #1 Chapter 4: Guided and Wireless Transmission
  • Text #1 Chapter 5: Signal-Encoding Techniques
  • Text #1 Chapter 6: Digital Data Communication Techniques
  • Text #1 Chapter 7: Data Link Control
  • Text #1 Chapter 8: Multiplexing
  • Text #1 Chapter 9: Spread Spectrum
  • Text #1 Chapter 10: Circuit Switching and Packet Switching
  • Text #1 Chapter 11: Asynchronous Transfer Mode
  • Text #1 Chapter 14: Cellular Wireless Networks
  • Text #1 Chapter 15: Local Area Networks Overview
  • Text #1 Chapter 16: High Speed LANs
  • Text #1 Chapter 17: Wireless LANs
  • Text #1 Chapter 18 and Chapter 19 (section 19.2 only): Internetwork Protocols and Operation or Text #2 Chapter 4: Network Layer and Routing (exclude sections 4.8 and 4.9)
  • Text #1 Chapter 22: Distributed Applications
  • Text #1 Chapter 20: Transport Protocols or Text #2 Chapter 3: Transport Layer or Text #2 Chapter 2: Application Layer
  • Text #1 Appendix 8: Fourier Analysis

(questions will include both computability theory and formal language theory)

Textbooks

  • Michael Sipser, Introduction to the Theory of Computation (Any Edition).
  • Peter Linz, An Introduction to Formal Languages and Automata, 5th Edition.
  • Dexter C. Kozen, Automata and Computability.

Formal Language Theory

Topics Subtopics Sipser Linz Kozen
Introductory Material Why Formal Languages; Sets, Alphabets, Languages Sec 0.2 Sec 1.2 Chapter 1
Finite Automata Basic Definitions; Deterministic FA; Nondeterministic FA; Epsilon-Transition Sec 1.1, 1.2 Sec 2.1; Sec 2.1; Sec 2.2 Chapter 3; Chapter 5
Regular Languages Regular Expressions; From Reg. exp. to FA Sec 1.3 Sec 3.1; Sec 3.2 Chapter 9
Context-Free Languages Context-Free Grammars; Derivations, Parsing, Trees Regular Grammars; Chomsky Normal Form Sec 2.1 Sec 5.1; Sec 5.1; Sec 3.3; Sec 6.2 Chapter19; Chapter 21
Push-Down Automata From CFG to PDA Sec 2.2 Sec 7.2 Chapter 24

Computability Theory

Topics Subtopics Sipser Linz Kozen
Turing Machines Basic Definitions; Variations of TM; Church Turing Thesis Chapter 3 Sec 9.1; Chapter 10; Sec 9.3 Chapter 28, 29, 30
Decidability Decidable Problems; The Halting Problem Chapter 4 Chapter 12

Complexity Theory

Topics Subtopics Sipser Linz Kozen
Time Complexity Measuring Complexity; The Class P; The Class NP; NP-Completeness; Additional NP-complete Prbs Sec 7.1; Sec 7.2; Sec 7.3; Sec 7.4; Sec 7.5 Chapter 14
Space Complexity The class PSPASE Sec 8.2

Brooklyn. All in.

Apply Now
Contact Us