Idea Transcript
GeeksforGeeks
A computer science portal for geeks
Practice GATE CS Placements Videos Contribute
Custom Search
Login/Register
GATE CS Notes according to GATE 2018 official Syllabus This page contains GATE CS Preparation Notes / Tutorials on Mathematics, Digital Logic, Computer Organization and Architecture, Programming and Data Structures, Algorithms, Theory of Computation, Compiler Design, Operating Systems, DBMS (Database Management Systems), and Computer Networks listed according to the GATE CS 2018 official Syllabus. GATE 2018 SYLLABUS
Section 1: Numerical and Verbal
LEARN
PRACTICE
1. Numerical Ability :
Ability
1. Numerical Ability :
Placements
Numerical Ability : Numerical
Book – Quantitative
2. Verbal Ability :
Placements | English | Error
Aptitude by R.S.
Placements
Aggarwal 2. Verbal Ability :
Detection and Correction
numerical estimation, numerical
Placements | English |
reasoning and data interpretation
Notes – English
Passage/Sentence Re-
Verbal Ability : English grammar,
arrangement
sentence completion,
Placements | English | Fill in the
verbal analogies, word groups,
Blanks
instructions,
Placements | English |
critical reasoning and verbal
Comprehension Passages
deduction
Section 2: Mathematics
1. Numerical Ability :
Placements
2. Verbal Ability :
computation,
EXTERNAL RESOURCES
1. Discrete Mathematics :
1. Discrete Mathematics :
1. Discrete Mathematics :
Representation of Boolean
Propositional and First
MIT – Discrete
Functions
Order Logic
Mathematics Video
Propositional and first order
Properties of Boolean algebra
Set Theory & Algebra
Lectures
logic
Functional Completeness
Combinatorics
Notes – First Order
Sets, relations, functions,
Introduction to Propositional Logic
Graph Theory
Logic
partial orders and lattices.
Set 1
Groups
Introduction to Propositional Logic
Combinatorics: counting,
Set 2
recurrence relations,
Propositional Equivalence
generating functions
Predicates and Quantifiers Set 1
Graphs: connectivity,
Predicates and Quantifiers Set 2
matching, coloring
Rules of Inference
1. Discrete Mathematics :
2. Linear Algebra :
2. Linear Algebra :
Book – Schaum’s
Linear Algebra
PDF
3. Probability :
MIT – Lecture Notes
Probability
IISC – Video
4. Calculus :
Lectures
Calculus
IITM – link for counting 2. Linear Algebra :
Combinatorics Basics
Matrices, determinants
Pigeonhole Principle
MIT – Linear Algebra
LU decomposition
PnC and Binomial Coefficients
Book – Linear
System of linear equations
Generalized PnC Set 1
Algebra
Eigenvalues and
Generalized PnC Set 2
3. Probability :
eigenvectors
Set Theory | Introduction
Book – Probability
Set Theory | Set Operations
Notes – Probability
3. Probability : Random variables
Relations and their types
Mean, median, mode and
Relations and their
MIT – Video
standard deviation
representations
Lectures
Uniform, normal, exponential,
Closure of Relations and
Notes – Calculus
Poisson and binomial
Equivalence Relations
Calculus
distributions
Functions | Properties and Types
Conditional probability and
Groups
Bayes theorem
Partial Orders and Lattices
4. Calculus :
4. Calculus :
Graph Theory Basics
Limits, Continuity and
Graph Isomorphisms and
Differentiability
Connectivity
Maxima and Minima. Mean
Planar Graphs and Graph
value theorem
Coloring
Integration
Euler and Hamiltonian Paths Matching (graph theory) Graph theory practice questions Recurrence relations 2. Linear Algebra : Matrix Introduction L U Decomposition Doolittle Algorithm : LU Decomposition System of Linear Equations Eigen Values and Eigen Vectors 3. Probability : Random Variables Probability Distributions Set 1 Mean, Variance And Standard Deviation Conditional Probability Bayes’s formula for Conditional Probability 4. Calculus : Limits, Continuity and Differentiability Lagrange’s Mean Value Theorem Mean Value Theorem | Rolle’s Theorem CATEGORY ARCHIVES: ENGINEERING MATHEMATICS Last Minute Notes – Engineering Mathematics
Section 3: Algorithms
1. Asymptotic Analysis of Algorithms : Analysis of Algorithms | Set 1
Searching, sorting, hashing
1. Asymptotic Analysis of Algorithms :
(Asymptotic Analysis)
Asymptotic worst case time and
Analysis of Algorithms | Set 2
space complexity Algorithm design techniques : greedy, dynamic programming and Graph search, minimum spanning trees, shortest paths
MIT – Introduction to
Analysis of Algorithms
Algorithms
2. Recurrence Relations :
(Worst, Average and Best
Analysis of Algorithms
Book – CLRS Solutions
Cases)
(Recurrences)
Manual
Analysis of Algorithms | Set 3
divide and conquer
Algorithms :
Visual – Data Structures
3. Divide and Conquer :
(Asymptotic Notations)
MergeSort
and Algorithms.
Analysis of Algorithms | Set 4
Divide and Conquer
Video – GfG Videos
4. Greedy Techniques :
Notes – Big – O Notation
Analysis of Algorithm | Set 5
Graph Minimum
Notes – Master Theorem
(Amortized Analysis Introduction)
Spanning Tree
Notes – Extended Master
Analysis of algorithms | little o
Graph Shortest Paths
Theorem
and little omega notations
Greedy Algorithms
Notes – Master Theorem
(Analysis of Loops)
What does ‘Space Complexity’ mean?
Graph
Articles | Analysis of Algorithms
Graph Traversals
2. Recurrence Relations :
problems and answers
5. Graph Based Algorithms :
6. Dynamic Programing :
Analysis of Algorithm | Set 4 (Solving Recurrences) 3. Divide and Conquer :
Dynamic Programming 7. Searching, Sorting and Hashing :
Divide and Conquer | Set 1
Searching
(Introduction)
Sorting
Binary Search
Hashing
Why is Binary Search preferred
8. Misc :
over Ternary Search?
Misc
Merge Sort
Commonly Asked
Merge Sort for Linked Lists
Algorithm Interview
Merge Sort for Doubly Linked List
Questions | Set 1
How to make Mergesort to
Data Structures and
perform O(n) comparisons in
Algorithms | Set 1
best case?
Data Structures and
QuickSort
Algorithms | Set 2
Iterative Quick Sort
Data Structures and
QuickSort on Singly Linked List
Algorithms | Set 3
QuickSort on Doubly Linked List
Data Structures and
When does the worst case of
Algorithms | Set 4
Quicksort occur?
Data Structures and
Why Quick Sort preferred for
Algorithms | Set 5
Arrays and Merge Sort for Linked
Data Structures and
Lists?
Algorithms | Set 6
Write a program to calculate
Data Structures and
pow(x,n)
Algorithms | Set 7
Median of two sorted arrays
Data Structures and
Count Inversions in an array | Set
Algorithms | Set 8
1 (Using Merge Sort)
Data Structures and
Divide and Conquer | Set 2
Algorithms | Set 9
(Closest Pair of Points)
Data Structures and
Divide and Conquer | Set 5
Algorithms | Set 10
(Strassen’s Matrix Multiplication)
Data Structures and
Sort a nearly sorted (or K sorted)
Algorithms | Set 11
array
Data Structures and
Search in an almost sorted array
Algorithms | Set 12
K-th Element of Two Sorted
Data Structures and
Arrays
Algorithms | Set 13
K’th Smallest/Largest Element in
Data Structures and
Unsorted Array | Set 2 (Expected
Algorithms | Set 14
Linear Time)
Data Structures and
Searching and Sorting
Algorithms | Set 15
4. Greedy Techniques :
Data Structures and
Greedy Algorithms | Set 1
Algorithms | Set 16
(Activity Selection Problem)
Data Structures and
Job Sequencing Problem | Set 1
Algorithms | Set 17
(Greedy Algorithm)
Data Structures and
Greedy Algorithms | Set 3
Algorithms | Set 18
(Huffman Coding)
Data Structures and
Greedy Algorithms | Set 4
Algorithms | Set 19
(Efficient Huffman Coding for
Data Structures and
Sorted Input)
Algorithms | Set 20
Greedy Algorithms | Set 2
Data Structures and
(Kruskal’s Minimum Spanning
Algorithms | Set 21
Tree Algorithm)
Data Structures and
Greedy Algorithms | Set 5
Algorithms | Set 22
(Prim’s Minimum Spanning Tree
Data Structures and
(MST))
Algorithms | Set 23
Greedy Algorithms | Set 6
Data Structures and
(Prim’s MST for Adjacency List
Algorithms | Set 24
Representation)
Data Structures and
Applications of Minimum
Algorithms | Set 25
Spanning Tree Problem
Data Structures and
Greedy Algorithms | Set 7
Algorithms | Set 26
(Dijkstra’s shortest path
Data Structures and
algorithm)
Algorithms | Set 27
Greedy Algorithms | Set 8
Data Structures and
(Dijkstra’s Algorithm for
Algorithms | Set 28
Adjacency List Representation)
Data Structures and
Greedy Algorithm to find
Algorithms | Set 29
Minimum number of Coins
Data Structures and
Strongly Connected Components
Algorithms | Set 30
Greedy Algorithms
Data Structures and
5. Graph Based Algorithms :
Algorithms | Set 31
Graph and its representations
Data Structures and
Breadth First Traversal or BFS
Algorithms | Set 32
for a Graph
Data Structures and
Depth First Traversal or DFS for
Algorithms | Set 33
a Graph
Data Structures and
Applications of Depth First
Algorithms | Set 34
Search
Data Structures and
Detect Cycle in a Directed Graph
Algorithms | Set 35
Disjoint Set (Or Union-Find) | Set 1 (Detect Cycle in an Undirected Graph) Detect cycle in an undirected graph Topological Sorting Longest Path in a Directed Acyclic Graph Biconnected Components Bellman–Ford Algorithm Floyd Warshall Algorithm Shortest Path in Directed Acyclic Graph Some interesting shortest path questions | Set 1 Shortest path with exactly k edges in a directed and weighted graph Biconnected Components Biconnected graph Articulation Points (or Cut Vertices) in a Graph Check if a graph is strongly connected | Set 1 (Kosaraju using DFS) Bridges in a graph Transitive closure of a graph Graph Algorithms | DFS and BFS | Minimum Spanning Tree | Shortest Paths | Connectivity 6. Dynamic Programing : Dynamic Programming | Set 1 (Overlapping Subproblems Property) Dynamic Programming | Set 2 (Optimal Substructure Property) Dynamic Programming | Set 4 (Longest Common Subsequence) Dynamic Programming | Set 8 (Matrix Chain Multiplication) Dynamic Programming | Set 10 ( 0-1 Knapsack Problem) Dynamic Programming | Set 6 (Min Cost Path) Dynamic Programming | Set 25 (Subset Sum Problem) Dynamic Programming | Set 23 (Bellman–Ford Algorithm) Dynamic Programming | Set 16 (Floyd Warshall Algorithm) Total number of non-decreasing numbers with n digits Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree) Smallest power of 2 greater than or equal to n Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming) Travelling Salesman Problem | Set 2 (Approximate using MST) Dynamic Programming 7. Searching, Sorting and Hashing : Linear Search Linear Search vs Binary Search Selection Sort Bubble Sort Insertion Sort Heap Sort Radix Sort Counting Sort Hashing | Set 1 (Introduction) Hashing | Set 2 (Separate Chaining) Hashing | Set 3 (Open Addressing) Hash Table vs STL Map Advantages of BST over Hash Table 8. Misc : Find subarray with given sum | Set 2 (Handles Negative Numbers) Largest subarray with equal number of 0s and 1s Find four elements a, b, c and d in an array such that a+b = c+d Print all subarrays with 0 sum Given an array A[] and a number x, check for pair in A[] with sum as x Union and Intersection of two Linked Lists Find whether an array is subset of another array | Added Method 3 Count pairs with given sum Top 20 Hashing Technique based Interview Questions CATEGORY ARCHIVES: ALGORITHMS Last Minute Notes – Algorithms
Section 4: Programming and Data
1. Programming in C, Recursion :
Structures
Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs
Programming and Data
Recursion :
C Programming
Programming in C, Recursion
1. Programming in C,
Structures :
Recursion
Principle of programming
Tail Recursion
languages | Set 1
Recursive functions
C Language
2. Array, Stack, Queue :
Video – NPTEL lectures Visual – Data Structure Visualizations
Recursion
Arrays
C Language | Set 1
Stack
C Language | Set 2
Queue
C Language | Set 3
3. Linked Lists :
C Language | Set 4
Linked List
C Language | Set 5
4. Trees, Binary search trees, Binary
C Language | Set 6
heaps :
C Language | Set 7
Binary Tree
C Language | Set 8
Binary Search Tree
C Language | Set 9
Binary Heap
C Language | Set 10
5. Graphs :
2. Array, Stack, Queue :
Graph
Array
CATEGORY ARCHIVES: DATA
Stack
STRUCTURES
Queue
CATEGORY ARCHIVES: C
3. Linked Lists :
Last Minute Notes – DATA
Linked List 4. Trees, Binary search trees,
STRUCTURE Last Minute Notes – C/C++
Binary heaps : Binary Trees Tree Traversals Binary Search Trees Balanced Binary Search Trees Heap 5. Graphs : Graph Graph Traversals Commonly Asked Data Structure Interview Questions | Set 1
Section 5: Operating Systems Processes, threads, CPU
1. Processes, threads, CPU scheduling :
scheduling Inter process communication, deadlock Memory management and virtual memory File systems
Operating Systems :
scheduling : What happens when we turn on
Process Management
computer?
CPU Scheduling
Process Management |
concurrency and synchronization,
1. Processes, threads, CPU
Video – NPTEL Lectures Notes – VirginiaTech Univ. Web resource
2. Inter process
Introduction
communication, concurrency
Process Scheduler
and synchronization :
Process Management | CPU
Concurrency and
Scheduling
synchronization
Program for FCFS Scheduling |
Notes – Galvin Lecture Slides Book – William Stallings Practice Problems and Solutions
3. Deadlock :
Set 1
Notes – User and Kernel
Deadlock
Program for FCFS Scheduling |
Level Threads
4. Main memory management :
Set 2 (Processes with different
Notes – Virtual Memory
Memory Management
and Cache
5. Virtual memory :
arrival times) Convoy Effect in Operating
Virtual Memory |
Systems
Questions
Program for Round Robin
Notes – Segmentation and Paging Notes – Some Interesting
6. File system and disk
problems on Virtual
scheduling :
scheduling | Set 1
memory
Program for Shortest Job First
Input Output Systems
(or SJF) scheduling | Set 1 (Non-
UNIX – I Node
preemptive)
Commonly Asked
Program for Shortest Job First
Operating Systems
(SJF) scheduling | Set 2
Interview Questions | Set
(Preemptive)
1
Shortest Job First scheduling
Operating Systems | Set
with predicted burst time
1
Highest Response Ratio Next
Operating Systems | Set
(HRRN) Scheduling
2
Program for Priority Scheduling |
Operating Systems | Set
Set 1
3
Priority Scheduling with different
Operating Systems | Set
arrival time | Set 2
4
Multilevel Queue Scheduling
Operating Systems | Set
Multilevel Feedback Queue
5
Scheduling
Operating Systems | Set
Starvation and Aging in Operating
6
Systems
Operating Systems | Set
Operating System | Thread
7
Multi threading models
Operating Systems | Set
User Level thread Vs Kernel
8
Level thread
Operating Systems | Set
2. Inter process communication,
9
concurrency and synchronization:
Operating Systems | Set
Process Synchronization |
10
Introduction
Operating Systems | Set
Critical Section
11
Inter Process Communication
Operating Systems | Set
Semaphores in operating system
12
Mutex vs Semaphore
Operating Systems | Set
Lock variable synchronization
13
mechanism
Operating Systems | Set
Peterson’s Algorithm for Mutual
14
Exclusion | Set 1 (Basic C
Operating Systems | Set
implementation)
15
Peterson’s Algorithm for Mutual
Operating Systems | Set
Exclusion | Set 2 (CPU Cycles
16
and Memory Fence)
Operating Systems | Set
Peterson’s Algorithm (Using
17
processes and shared memory) Readers-Writers Problem | Set 1 (Introduction and Readers Preference Solution) Process Synchronization | Monitors Dining-Philosophers Solution Using Monitors Dining Philosopher Problem Using Semaphores Priority Inversion : What the heck ! What’s difference between Priority Inversion and Priority Inheritance ? 3. Deadlock : Process Management | Deadlock Introduction Deadlock Prevention And Avoidance Deadlock Detection And Recovery Resource Allocation Graph (RAG) Banker’s Algorithm Program for Banker’s Algorithm | Set 1 (Safety Algorithm) 4. Main memory management : Mapping virtual address to physical addresses Memory Management |Partition Allocation Method Paging Page Table Entries Segmentation Program for First Fit algorithm in Memory Management Program for Next Fit algorithm in Memory Management Working with Shared Libraries | Set 1 Static and Dynamic Libraries | Set 1 5. Virtual memory : Virtual Memory Page Fault Handling Page Replacement Algorithms Program for Optimal Page Replacement Algorithm What exactly Spooling is all about? Overlays in Memory Management 6. File system and disk scheduling : File Systems File Allocation Methods Difference between FAT32, exFAT, and NTFS File System Disk Scheduling Algorithms CATEGORY ARCHIVES: OPERATING SYSTEMS Last Minute Notes – Operating Systems
Section 6: Databases
1. ER model :
1. ER model :
Database Management System
ER model, Relational model :
– Introduction | Set 1
relational algebra, tuple calculus,
Database Management System
SQL
ER and Relational Models
DBMS Architecture 2-Level, 3-
control File organization, indexing (e.g., B and B+ trees)
Notes – Lecture Slides
algebra, tuple calculus) :
Silberschatz, Korth and
ER and Relational Models
Sudarshan
3. Database design (integrity
Architecture)
Transactions and concurrency
Video – NPTEL Lectures
2. Relational model (relational
Introduction | Set 2 (3-Tier
Integrity constraints, normal forms
Databases :
Level
Database Design(Normal
Need for DBMS
Forms)
Advantages of DBMS over File
Notes – Lecture Slides
constraints, normal forms) :
Raghu Ramakrishnan and Johannes Gehrke Notes – Stanford DBMS
4. Query languages (SQL) :
system
course Lecture Slides
SQL
Data Abstraction and Data
Notes – Jeff Ullman’s
5. Transactions and
Lecture Slides
concurrency control :
Independence ER Model
Transactions and
Minimization of ER Diagram
concurrency control
Enhanced ER Model
Notes – Normal forms Notes – Canonical Cover Notes – Indexing
6. File structures (sequential
Mapping from ER Model to
files, indexing, B and B+
Relational Model
trees) :
2. Relational model (relational algebra,
Visual – B Tree Notes – B+ Tree Visual – B+ Tree
File structures (sequential
tuple calculus) :
files, indexing, B and B+
Relational Model
trees)
Relational Algebra – Overview
Commonly asked DBMS
DBMS | Anomalies in Relational
interview questions | Set
Model
1
Relational Model Introduction and
Commonly asked DBMS
Codd Rules
interview questions | Set
Keys in Relational Model
2
(Candidate, Super, Primary,
Database Management
Alternate and Foreign)
Systems | Set 1
Relational Algebra-Basic
Database Management
Operators
Systems | Set 2
Relational Algebra – Extended
Database Management
Operators
Systems | Set 3
DBMS | How to solve Relational
Database Management
Algebra problems for GATE -1
Systems | Set 4
DBMS | How to solve Relational
Database Management
Algebra problems for GATE -2
Systems | Set 5
3. Database design (integrity
Database Management
constraints, normal forms) :
Systems | Set 6
Database Normalization |
Database Management
Introduction
Systems | Set 7
Database Normalization | Normal
Database Management
Forms
Systems | Set 8
Functional Dependency and
Database Management
Attribute Closure
Systems | Set 9
Finding Attribute Closure and
Database Management
Candidate Keys using Functional
Systems | Set 10
Dependencies
Database Management
Lossless Decomposition
Systems | Set 11
Dependency Preserving Decomposition Lossless Join and Dependency Preserving Decomposition DBMS | How to find the highest normal form of a relation Equivalence of Functional Dependencies Armstrong’s Axioms in Functional Dependency Canonical Cover 4. Query languages (SQL) : Structured Query Language (SQL) Inner VS Outer Join Having Vs Where Clause Nested Queries in SQL SQL Tutorial 5. Transactions and concurrency control : Concurrency Control Introduction Database Recovery Techniques ACID Properties in DBMS Conflict Serializability Precedence Graph For Testing Conflict Serializability How to test if two schedules are View Equal or not ? Recoverability of Schedules 6. File structures (sequential files, indexing, B and B+ trees) : Indexing in Databases | Set 1 B-Tree | Set 1 (Introduction) B-Tree | Set 2 (Insert) B-Tree | Set 3 (Delete) RAID Data Warehousing Data Mining CATEGORY ARCHIVES: DBMS Last Minute Notes – DBMS
Section 7: Computer Networks Concept of layering, LAN
1. Network Fundamental and Physical layer :
Computer Networks (Simplex,
IPv4/IPv6, routers and routing algorithms (distance vector, link state)
Application layer protocols (DNS,
Network Layer
Let’s experiment with Networking
IP Addressing
Network security : authentication, basics of public key digital signatures and certificates, firewalls
Tanenbaum Visual – Sliding Window
4. Transport layer :
Animation Notes – Sliding Window
5. Application layer :
P2P(Peer To Peer) File Sharing
HTTP Non-Persistent &
LAN Technologies | ETHERNET
Persistent Connection |
Ethernet Frame Format
Set 2 (Practice Question)
Efficiency of CSMA/CD
Application Layer
Computer Networks | Error
and private key cryptography,
on Computer Networks by
Transport Layer
2. Data Link layer :
Basics of Wi-Fi
Notes – Web Resources
3. Network layer :
TCP/IP Model
SMTP, POP, FTP, HTTP)
Kanpur
Data Link Layer
Half-Duplex and Full-Duplex) Layers of OSI Model
TCP/UDP and sockets, congestion
Notes – Lecture Notes IIT
2. Data Link layer :
Transmission Modes in
switching
Video – NPTEL Lectures
Computer Networks
Basics of Computer Networking
Flow and error control techniques,
Computer Networks :
Physical layer :
Network Topologies
technologies (Ethernet)
control
1. Network Fundamental and
MIT Notes – IPv4 vs iPv6
6. Network security :
Detection
Network Security
Stop and Wait ARQ
Commonly asked
Sliding Window Protocol | Set 1
Computer Networks
(Sender Side)
Interview Questions | Set
Sliding Window Protocol | Set 2
1
(Receiver Side)
Computer Networks | Set
Sliding Window Protocol | Set 3
1
(Selective Repeat)
Computer Networks | Set
Sliding Window protocols
2
Summary With Questions
Computer Networks | Set
Program to remotely Power On a
3
PC over the internet using the
Computer Networks | Set
Wake-on-LAN protocol
4
Program to calculate the Round
Computer Networks | Set
Trip Time (RTT)
5
Introduction of MAC Address
Computer Networks | Set
Collision Avoidance in wireless
6
networks
Computer Networks | Set
3. Network layer :
7
Line Configuration in Computer
Computer Networks | Set
Networks
8
Difference between Unicast,
Computer Networks | Set
Broadcast and Multicast
9
Collision Domain and Broadcast
Computer Networks | Set
Domain
10
IP Addressing | Introduction and
Computer Networks | Set
Classful Addressing
11
Network Layer | Introduction and
Computer Networks | Set
IPv4 Datagram Header
12
Network Layer | Ipv4 Datagram Fragmentation and Delays Internet Protocol v6 | IPv6 Internet Protocol version 6 (IPv6) Header IP Addressing | Classless Addressing Computer Networks | Longest Prefix Matching in Routers Program to determine class, Network and Host ID of an IPv4 address C Program to find IP Address, Subnet Mask & Default Gateway Routing v/s Routed Protocols Onion Routing Routing Protocols Set 1 (Distance Vector Routing) Route Poisoning and Count to infinity problem Internet Control Message Protocol (ICMP) | Computer Networks Circuit Switching Packet Switching and Delays Differences between Virtual Circuits & Datagram Networks Computer Network | Circuit Switching VS Packet Switching Traceroute How ARP works? ARP, Reverse ARP(RARP), Inverse ARP(InARP), Proxy ARP and Gratuitous ARP What’s difference between Ping and Traceroute? 4. Transport layer : Congestion Control Leaky Bucket Algorithm TCP Congestion Control TCP 3-Way Handshake Process TCP Connection Termination Error Control in TCP TCP Timers User Datagram Protocol (UDP) Multiplexing and Demultiplexing in Transport Layer 5. Application layer : Protocols in Application Layer DNS (Domain Name Server) | NetWorking Why does DNS use UDP and not TCP? How DHCP server dynamically assigns IP address to a host? Simple Mail Transfer Protocol (SMTP) File Transfer Protocol (FTP) HTTP Non-Persistent & Persistent Connection What’s difference between http:// and https:// ? What’s difference between HTML and HTTP ? What’s difference between The Internet and The Web ? Basics of Wi-Fi Wi-Fi Password of All Connected Networks in Windows/Linux Network Devices (Hub, Repeater, Bridge, Switch, Router and Gateways) 6. Network security : Basic Network Attacks Introduction to Firewall Deniel of Service and Prevention Digital Signatures and Certificates LZW (Lempel–Ziv–Welch) Compression technique RSA Algorithm in Cryptography Implementation of Diffie-Hellman Algorithm Unicode CATEGORY ARCHIVES: COMPUTER NETWORKS Last Minute Notes – Computer Networks
Section 8: Computer Organization and Architecture
1. Machine instructions and addressing modes :
ALU, data path and control unit
Addressing Modes 2. ALU, data path and control unit : Hardwired v/s Micro-
Instruction pipelining Memory hierarchy: cache, main memory and secondary storage
Computer Organization and
Architecture :
Architecture :
Machine Instructions
Machine instructions and addressing modes
Computer Organization and
Quiz on Microprocessors
Video – NPTEL Lectures
Computer Organization and
Book – Carl Hamacher
Architecture
Book – Morris Mano Notes – Pipelining
programmed Control Unit
Notes – Cache Memory
3. Instruction pipelining :
I/O interface (Interrupt and DMA mode)
Pipelining | Set 1 (Execution,
Notes – Cache
Stages and Throughput)
Associativity
Pipelining | Set 2 (Dependencies and Data Hazard) Pipelining | Set 3 (Types and Stalling) 4. Cache Memory : Cache Memory Cache Organization | Introduction What’s difference between CPU Cache and TLB? 5. I/O interface (Interrupt and DMA mode) : I/O Interface (Interrupt and DMA Mode) Priority Interrupts | (S/W Polling and Daisy Chaining) CATEGORY ARCHIVES: COMPUTER ORGANIZATION & ARCHITECTURE
Section 9: Theory of Computation Regular expressions and finite
1. Regular expression, langauges, grammar and finite automata : Introduction of Theory of
automata Context-free grammars and pushdown automata languages, pumping lemma Turing machines and undecidability
Theory of Computation :
langauges, grammar and
Video – NPTEL Lectures
finite automata :
Computation
Regular languages and
Finite Automata | Introduction
finite automata
Notes – NFA and DFA Notes – Non Regular language
2. Context free langauges,
Chomsky Hierarchy
Regular and context-free
1. Regular expression,
Regular Expressions, Regular
grammar and push down
Grammar and
automata :
Notes – PDA Notes – Turing Machine Notes – Rice Theorem
Regular Languages
Context free languages
Pumping Lemma
and Push-down automata
Designing Finite Automata from
3. Context Sensitive langauges :
Regular Expression Conversion from NFA to DFA
. 4. Turing machines and
Minimization of DFA Union & Intersection of Regular
undecidability :
languages with CFL
Recursively enumerable
Mealy and Moore Machines
sets and Turing machines
2. Context free langauges, grammar
Undecidability
and push down automata :
Automata Theory
Pushdown Automata
Automata Theory | Set 1
Closure Properties of Context
Automata Theory | Set 2
Free Languages
Automata Theory | Set 3
Ambiguity in CFG and CFL
Automata Theory | Set 4
Simplifying Context Free
Automata Theory | Set 5
Grammars
Automata Theory | Set 6
3. Context Sensitive langauges : Context-sensitive Grammar (CSG) and Language (CSL) 4. Turing machines and undecidability : Recursive and Recursive Enumerable Languages Turing Machine Decidability Undecidability and Reducibility CATEGORY ARCHIVES: THEORY OF COMPUTATION & AUTOMATA Last Minute Notes – Theory of Computation
Section 10: Compiler Design Lexical analysis, parsing, syntaxdirected translation Runtime environments Intermediate code generation
1. Introduction of Compiler :
1. Introduction of Compiler :
Static and Dynamic Scoping
Compiler Design :
MCQ on Memory
2. Lexical analysis :
Video – Stanford Lectures
allocation and compilation
Lexical Analysis
Book – Basics of
process
C program to detect tokens in a
Compiler Design
2. Lexical analysis :
C program
Notes – Bivas Mitra IITgp
Lexical analysis
3. Parsing :
Notes – LR Parsing
3. Parsing :
Classification of Context Free
Compiler Theory | Set 1
Grammars
Compiler Theory | Set 2
Ambiguous Grammar
Translation Notes – Intermediate
4. Syntax directed transalation :
Why FIRST and FOLLOW?
Parsing and Syntax
FIRST Set in Syntax Analysis
directed translation
FOLLOW Set in Syntax Analysis
Notes – Syntax Directed
Code Generation
5. Runtime environments :
Introduction to Syntax Analysis
. 6. Intermediate code generation
Parsing Set 1
:
Parsing Set 2 Parsing Set 3
Code Generation and
4. Syntax directed transalation :
Optimization
Syntax Directed Translation 5. Runtime environments : Runtime Environments 6. Intermediate code generation : Intermediate Code Generation Code Optimization Introduction of Object Code CATEGORY ARCHIVES: COMPILER DESIGN Last Minute Notes – Compiler Design
Section 11: Digital Logic Boolean algebra Combinational and sequential circuits. Minimization Number representations and computer arithmetic (fixed and floating point)
1. Introduction of Boolean Algebra and
Digital Logic :
Digital Logic :
Logic Gates : Logic Gates
Digital Logic (101)
Video – NPTEL Lectures
Properties of Boolean algebra
Number representation
Notes – Number System-
Minimization of Boolean
Swarthmore
Functions
Notes – IEEE Standard
Representation of Boolean
754 Floating Point
Functions
Numbers
Canonical and Standard Form Functional Completeness K-Map 2. Combinational Circuits : Half Adder Full Adder Half Subtractor Full Subtractor Half Adder and Half Subtractor using NAND NOR gates Encoder Binary Decoder Multiplexers Read-Only Memory (ROM) 3. Sequential Circuits : Introduction of Sequential Circuits Flip-flop types and their Conversion Synchronous Sequential Circuits Counters 4. Number Representation and Computer Airthmetic : Number System and base conversions Code Converters – BCD(8421) to/from Excess-3 Code Converters – Binary to/from Gray Code Program for Decimal to Binary Conversion Program for Binary To Decimal Conversion Program for Decimal to Octal Conversion Program for Octal to Decimal Conversion Program for Hexadecimal to Decimal Conversion Computer Arithmetic | Set – 1 Computer Arithmetic | Set – 2 Floating Point Representation What’s difference between 1’s Complement and 2’s Complement? CATEGORY ARCHIVES: DIGITAL ELECTRONICS & LOGIC DESIGN Last Minute Notes – Digital Electronics
Last Updated on : 14th November, 2017
Other Useful Links : 1. Important Topics for GATE 2018 Computer Science 2. Last Minute Notes – GATE 2018 3. Top 5 Topics for Each Section of GATE CS Syllabus 4. GATE CS 2018 Syllabus 5. GATE CS 2018 Important Dates 6. Articles on Computer Science 7. Previous year papers GATE CS, solutions and explanations year-wise and topic-wise. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above!
Company Wise Coding Practice Topic Wise Coding Practice
Load Comments
@geeksforgeeks, Some rights reserved Contact Us! About Us! Careers! Privacy Policy