Mathematical Logic For Computer Science Gate Pdf

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, Database Management Systems (DBMS), and Computer Networks listed according to the GATE CS 2021 syllabus.

Attend daily free live GATE CS classes on GeeksforGeeks GATE CS Channel.

GATE 2020 Syllabus	Learn	Practice	External Resources
Section 1: General Aptitude (GA) Verbal Aptitude : Basic English grammar: tenses, articles, adjectives, prepositions, conjunctions, verb-noun agreement, and other parts of speech Basic vocabulary: words, idioms, and phrases in context Reading and comprehension Narrative sequencing Quantitative Aptitude : Data interpretation: data graphs (bar graphs, pie charts, and other graphs representing data), 2- and 3-dimensional plots, maps, and tables Numerical computation and estimation: ratios, percentages, powers, exponents and logarithms, permutations and combinations, and series Mensuration and geometry Elementary statistics and probability Analytical Aptitude : Logic: deduction and induction Analogy Numerical relations and reasoning Spatial Aptitude : Transformation of shapes: translation, rotation, scaling, mirroring, assembling, and grouping Paper folding, cutting, and patterns in 2 and 3 dimensions	Numerical Ability : Placements Verbal Ability : Placements | English | Error Detection and Correction Placements | English | Passage/Sentence Re-arrangement Placements | English | Fill in the Blanks Placements | English | Comprehension Passages	Numerical Ability : Placements Verbal Ability : Placements	Numerical Ability : Book – Quantitative Aptitude by R.S. Aggarwal Verbal Ability : Notes – English
Section 2: Mathematics Discrete Mathematics : Propositional and first order logic Sets, relations, functions, partial orders and lattices. Monoids, Groups Combinatorics: counting, recurrence relations, generating functions Graphs: connectivity, matching, coloring Linear Algebra : Matrices, determinants LU decomposition System of linear equations Eigenvalues and eigenvectors Probability : Random variables Mean, median, mode and standard deviation Uniform, normal, exponential, Poisson and binomial distributions Conditional probability and Bayes theorem Calculus : Limits, Continuity and Differentiability Maxima and Minima. Mean value theorem Integration	Discrete Mathematics : Representation of Boolean Functions Properties of Boolean algebra PDNF and PCNF in Discrete Mathematics Functional Completeness Introduction to Propositional Logic Set 1 Introduction to Propositional Logic Set 2 Propositional Equivalence Predicates and Quantifiers Set 1 Predicates and Quantifiers Set 2 Some theorems on Nested Quantifiers Rules of Inference Consensus theorem Introduction to Proofs Combinatorics Basics Pigeonhole Principle PnC and Binomial Coefficients Generalized PnC Set 1 Generalized PnC Set 2 Inclusion-Exclusion and its various Applications Corollaries of Binomial Theorem Introduction of Generating Functions Generating Functions – Set 2 Set Theory | Introduction Set Theory | Set Operations Power Set and its Properties Relations and their types Relations and their representations Representing Relations Closure of Relations and Equivalence Relations Functions | Properties and Types Inverse functions and composition of functions Total number of possible functions Number of possible equivalence relations Groups Partial Orders and Lattices Hasse Diagrams Graph Theory Basics – Set 1 Graph Theory Basics – Set 2 Walks, Trails, Paths, Cycles and Circuits in Graph Number of nodes and height of binary tree Graph measurements: length, distance, diameter, eccentricity, radius, center Graph Isomorphisms and Connectivity Planar Graphs and Graph Coloring Euler and Hamiltonian Paths Independent Sets, Covering and Matching Matching (graph theory) Graph theory practice questions Recurrence relations Different types of recurrence relations and their solutions Types of Recurrence Relations – Set 2 Linear Algebra : Matrix Introduction Different operations on matrices L U Decomposition Doolittle Algorithm : LU Decomposition System of Linear Equations Eigen Values and Eigen Vectors Probability : Probability Random Variables Mean, Variance And Standard Deviation Law of total probability Bayes's formula for Conditional Probability Probability Distributions Set 1 (Uniform Distribution) Probability Distributions Set 2 (Exponential Distribution) Probability Distributions Set 3 (Normal Distribution) Probability Distributions Set 4 (Binomial Distribution) Probability Distributions Set 5 (Poisson Distribution) Hypergeometric Distribution model Conditional Probability Covariance and Correlation Calculus : Limits, Continuity and Differentiability Lagrange's Mean Value Theorem Mean Value Theorem | Rolle's Theorem Cauchy's mean value theorem Indefinite Integrals Finding nth term of any polynomial sequence Sequence, Series and Summations CATEGORY ARCHIVES: ENGINEERING MATHEMATICS Last Minute Notes – Engineering Mathematics	Discrete Mathematics : Propositional and First Order Logic Set Theory & Algebra Combinatorics Combinatorics | Set 1 Combinatorics | Set 2 Graph Theory Linear Algebra : Linear Algebra Probability : Probability Calculus : Calculus	Discrete Mathematics : Video – MIT Discrete Mathematics Lectures Notes – First Order Logic Book – Schaum's PDF MIT – Lecture Notes IISC – Video Lectures IITM – link for counting Papers – GATE's Explanation by NPTEL Linear Algebra : MIT – Linear Algebra Book – Linear Algebra Probability : Book – Probability Notes – Probability Calculus : MIT – Video Lectures Notes – Calculus Calculus
Section 3: Algorithms Searching, sorting, hashing Asymptotic worst case time and space complexity Algorithm design techniques : greedy, dynamic programming and divide‐and‐conquer Graph traversals, minimum spanning trees, shortest paths	Asymptotic Analysis of Algorithms : Analysis of Algorithms | Set 1 (Asymptotic Analysis) Analysis of Algorithms | Set 2 (Worst, Average and Best Cases) Analysis of Algorithms | Set 3 (Asymptotic Notations) Analysis of Algorithms | Set 4 (Analysis of Loops) Analysis of Algorithm | Set 5 (Amortized Analysis Introduction) Analysis of algorithms | little o and little omega notations What does 'Space Complexity' mean? Articles | Analysis of Algorithms Recurrence Relations : Analysis of Algorithm | Set 4 (Solving Recurrences) Different types of recurrence relations and their solutions Divide and Conquer : Divide and Conquer | Set 1 (Introduction) Binary Search Why is Binary Search preferred over Ternary Search? Merge Sort Merge Sort for Linked Lists Merge Sort for Doubly Linked List How to make Mergesort to perform O(n) comparisons in best case? QuickSort Iterative Quick Sort QuickSort on Singly Linked List QuickSort on Doubly Linked List When does the worst case of Quicksort occur? Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists? Write a program to calculate pow(x,n) Median of two sorted arrays Count Inversions in an array | Set 1 (Using Merge Sort) Divide and Conquer | Set 2 (Closest Pair of Points) Divide and Conquer | Set 5 (Strassen's Matrix Multiplication) Sort a nearly sorted (or K sorted) array Search in an almost sorted array K-th Element of Two Sorted Arrays K'th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time) Searching and Sorting Greedy Techniques : Greedy Algorithms | Set 1 (Activity Selection Problem) Job Sequencing Problem | Set 1 (Greedy Algorithm) Greedy Algorithms | Set 3 (Huffman Coding) Greedy Algorithms | Set 4 (Efficient Huffman Coding for Sorted Input) Greedy Algorithms | Set 2 (Kruskal's Minimum Spanning Tree Algorithm) Greedy Algorithms | Set 5 (Prim's Minimum Spanning Tree (MST)) Greedy Algorithms | Set 6 (Prim's MST for Adjacency List Representation) Applications of Minimum Spanning Tree Problem Greedy Algorithms | Set 7 (Dijkstra's shortest path algorithm) Greedy Algorithms | Set 8 (Dijkstra's Algorithm for Adjacency List Representation) Greedy Algorithm to find Minimum number of Coins Strongly Connected Components Greedy Algorithms Graph Based Algorithms : Graph and its representations Breadth First Traversal or BFS for a Graph Depth First Traversal or DFS for a Graph Applications of Depth First Search Detect Cycle in a Directed Graph 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 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 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 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	Asymptotic Analysis of Algorithms : Analysis of Algorithms Recurrence Relations : Analysis of Algorithms (Recurrences) Practice Set for Recurrence Relations Divide and Conquer : MergeSort Divide and Conquer Greedy Techniques : Graph Minimum Spanning Tree Graph Shortest Paths Greedy Algorithms Graph Based Algorithms : Graph Graph Traversals Dynamic Programing : Dynamic Programming Searching, Sorting and Hashing : Searching Sorting Hashing Misc : Misc Commonly Asked Algorithm Interview Questions | Set 1 Data Structures and Algorithms | Set 1 Data Structures and Algorithms | Set 2 Data Structures and Algorithms | Set 3 Data Structures and Algorithms | Set 4 Data Structures and Algorithms | Set 5 Data Structures and Algorithms | Set 6 Data Structures and Algorithms | Set 7 Data Structures and Algorithms | Set 8 Data Structures and Algorithms | Set 9 Data Structures and Algorithms | Set 10 Data Structures and Algorithms | Set 11 Data Structures and Algorithms | Set 12 Data Structures and Algorithms | Set 13 Data Structures and Algorithms | Set 14 Data Structures and Algorithms | Set 15 Data Structures and Algorithms | Set 16 Data Structures and Algorithms | Set 17 Data Structures and Algorithms | Set 18 Data Structures and Algorithms | Set 19 Data Structures and Algorithms | Set 20 Data Structures and Algorithms | Set 21 Data Structures and Algorithms | Set 22 Data Structures and Algorithms | Set 23 Data Structures and Algorithms | Set 24 Data Structures and Algorithms | Set 25 Data Structures and Algorithms | Set 26 Data Structures and Algorithms | Set 27 Data Structures and Algorithms | Set 28 Data Structures and Algorithms | Set 29 Data Structures and Algorithms | Set 30 Data Structures and Algorithms | Set 31 Data Structures and Algorithms | Set 32 Data Structures and Algorithms | Set 33 Data Structures and Algorithms | Set 34 Data Structures and Algorithms | Set 35	Algorithms : Video – GeeksforGeeks Videos Video – Lectures by Ravindrababu Ravula MIT – Introduction to Algorithms Book – CLRS Solutions Manual Visual – Data Structures and Algorithms. Notes – Big – O Notation Notes – Master Theorem Notes – Extended Master Theorem Notes – Master Theorem problems and answers
Section 4: Programming and Data Structures Programming in C, Recursion Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs	Programming in C, Recursion : C Programming Recursion Tail Recursion Recursive functions Array, Stack, Queue : Arrays Stack Queue Linked Lists : Linked List Trees, Binary search trees, Binary heaps : Binary Tree Binary Search Tree Binary Heap Graphs : Graph CATEGORY ARCHIVES: DATA STRUCTURES CATEGORY ARCHIVES: C Last Minute Notes – DATA STRUCTURE Last Minute Notes – C/C++	Programming in C, Recursion : Principle of programming languages | Set 1 C Language Recursion C Language | Set 1 C Language | Set 2 C Language | Set 3 C Language | Set 4 C Language | Set 5 C Language | Set 6 C Language | Set 7 C Language | Set 8 C Language | Set 9 C Language | Set 10 Array, Stack, Queue : Array Stack Queue Linked Lists : Linked List Trees, Binary search trees, Binary heaps : Binary Trees Tree Traversals Binary Search Trees Balanced Binary Search Trees Heap Graphs : Graph Graph Traversals Commonly Asked Data Structure Interview Questions | Set 1	Programming and Data Structures : Video – NPTEL lectures Visual – Data Structure Visualizations
Section 5: Operating Systems Processes, System calls, threads, CPU scheduling Inter‐process communication, concurrency and synchronization, deadlock Memory management and virtual memory I/O scheduling, File systems	Processes, threads, CPU scheduling : What happens when we turn on computer? Introduction of Operating System Functions of Operating System Types of Operating Systems Dual Mode operations in OS Privileged and Non-Privileged Instructions 32-bit and 64-bit operating systems Real time systems Operating Systems | Need and Functions Process Management | Introduction States of a process Process Table and Process Control Block (PCB) Process Scheduler Difference between dispatcher and scheduler Process Management | CPU Scheduling Preemptive and Non-Preemptive Scheduling Program for FCFS Scheduling | Set 1 Program for FCFS Scheduling | Set 2 (Processes with different arrival times) Convoy Effect in Operating Systems Program for preemptive priority CPU scheduling Program for Round Robin scheduling | Set 1 Round Robin Scheduling with different arrival times Program for Shortest Job First (or SJF) scheduling | Set 1 (Non- preemptive) Program for Shortest Job First (SJF) scheduling | Set 2 (Preemptive) Shortest Job First scheduling with predicted burst time Longest Remaining Time First (LRTF) algorithm Longest Remaining Time First (LRTF) Program Highest Response Ratio Next (HRRN) Scheduling Program for Priority Scheduling | Set 1 Priority Scheduling with different arrival time | Set 2 Multilevel Queue Scheduling Multilevel Feedback Queue Scheduling Multiple-Processor Scheduling Measure the time spent in context switch Starvation and Aging in Operating Systems Introduction of System Call Operating System | Thread Threads and its types Multithreading Multi threading models Benefits of Multithreading Process-based and Thread-based Multitasking User Level thread Vs Kernel Level thread Microkernel Monolithic Kernel and key differences from Microkernel Difference between multitasking, multithreading and multiprocessing fork() in C Boot Block Inter‐process communication, concurrency and synchronization: Process Synchronization | Introduction Operating System | Process Synchronization | Set 2 Critical Section Inter Process Communication IPC using Message Queues IPC through shared memory Interprocess Communication: Methods Semaphores in operating system Mutex vs Semaphore Lock variable synchronization mechanism Peterson's Algorithm for Mutual Exclusion | Set 1 (Basic C implementation) Peterson's Algorithm for Mutual Exclusion | Set 2 (CPU Cycles and Memory Fence) Peterson's Algorithm (Using processes and shared memory) Readers-Writers Problem | Set 1 (Introduction and Readers Preference Solution) Reader-Writers solution using Monitors Producer Consumer Problem using Semaphores | Set 1 Producer-Consumer solution using Semaphores in Java | Set 2 Sleeping Barber problem Process Synchronization | Monitors Dining-Philosophers Solution Using Monitors Dining Philosopher Problem Using Semaphores Dekker's algorithm Bakery Algorithm Priority Inversion : What the heck ! What's difference between Priority Inversion and Priority Inheritance ? Deadlock, Starvation, and Livelock Deadlock : Process Management | Deadlock Introduction Program for Deadlock free condition Deadlock Prevention And Avoidance Deadlock Detection And Recovery Resource Allocation Graph (RAG) Banker's Algorithm Program for Banker's Algorithm | Set 1 (Safety Algorithm) Banker's Algorithm : Print all the safe state Deadlock detection algorithm Methods of resource allocation to processes by operating system Main memory management : Mapping virtual address to physical addresses Logical vs Physical Address in Operating System Paging Page Table Entries Inverted Page Table Segmentation Memory Management | Partition Allocation Method Program for First Fit algorithm in Memory Management Program for Next Fit algorithm in Memory Management Non-Contiguous Allocation Fixed (or static) Partitioning Variable (or dynamic) Partitioning Working with Shared Libraries | Set 1 Static and Dynamic Libraries | Set 1 Buddy System Buddy System Memory Allocation Buddy System Memory Deallocation Allocating kernel memory Requirements of memory management system Virtual memory : Virtual Memory Secondary memory – Hard disk drive Page Fault Handling Page Replacement Algorithms Belady's Anomaly Program for Optimal Page Replacement Algorithm Second Chance (or Clock) Page Replacement Policy Techniques to handle Thrashing What exactly Spooling is all about? Difference between Spooling and Buffering Overlays in Memory Management Swap Space File system and disk scheduling : File Systems Structures of Directory File Directory | Path Name File Access Methods File Allocation Methods Operating System | Free space management Difference between FAT32, exFAT, and NTFS File System Disk Scheduling Algorithms Program for SSTF disk scheduling algorithm CATEGORY ARCHIVES: OPERATING SYSTEMS Last Minute Notes – Operating Systems	Processes, threads, CPU scheduling : Process Management CPU Scheduling Inter‐process communication, concurrency and synchronization : Concurrency and synchronization Deadlock : Deadlock Main memory management : Memory Management Virtual memory : Virtual Memory | Questions File system and disk scheduling : Input Output Systems UNIX – I Node Commonly Asked Operating Systems Interview Questions | Set 1 Operating Systems | Set 1 Operating Systems | Set 2 Operating Systems | Set 3 Operating Systems | Set 4 Operating Systems | Set 5 Operating Systems | Set 6 Operating Systems | Set 7 Operating Systems | Set 8 Operating Systems | Set 9 Operating Systems | Set 10 Operating Systems | Set 11 Operating Systems | Set 12 Operating Systems | Set 13 Operating Systems | Set 14 Operating Systems | Set 15 Operating Systems | Set 16 Operating Systems | Set 17	Operating Systems : Video – NPTEL Lectures Video – Lectures by Ravindrababu Ravula Notes – VirginiaTech Univ. Web resource Notes – Galvin Lecture Slides Book – William Stallings Practice Problems and Solutions Notes – User and Kernel Level Threads Notes – Virtual Memory and Cache Notes – Segmentation and Paging Notes – Some Interesting problems on Virtual memory
Section 6: Databases ER‐model, Relational model : relational algebra, tuple calculus, SQL Integrity constraints, normal forms Transactions and concurrency control File organization, indexing (e.g., B and B+ trees)	ER‐model : Database Management System – Introduction | Set 1 Database Management System Introduction | Set 2 (3-Tier Architecture) DBMS Architecture 2-Level, 3-Level Need for DBMS Advantages of DBMS over File system Choice of DBMS | Economic factors Data Abstraction and Data Independence ER Model Recursive Relationships Minimization of ER Diagram Enhanced ER Model Mapping from ER Model to Relational Model Relational model (relational algebra, tuple calculus) : Relational Model Relational Algebra – Overview DBMS | Anomalies in Relational Model Relational Model Introduction and Codd Rules Keys in Relational Model (Candidate, Super, Primary, Alternate and Foreign) Relational Algebra-Basic Operators Relational Algebra – Extended Operators Tupple Relational Calculus DBMS | How to solve Relational Algebra problems for GATE DBMS | Row oriented vs. column oriented data stores Database design (integrity constraints, normal forms) : Database Normalization | Introduction Database Normalization | Normal Forms Functional Dependency and Attribute Closure Finding Attribute Closure and Candidate Keys using Functional Dependencies Number of possible Superkeys Lossless Decomposition Dependency Preserving Decomposition Lossless Join and Dependency Preserving Decomposition DBMS | How to find the highest normal form of a relation DBMS | Minimum relations satisfying 1NF Equivalence of Functional Dependencies Armstrong's Axioms in Functional Dependency Canonical Cover Denormalization in Databases Introduction of 4th and 5th Normal form Query languages (SQL) : Structured Query Language (SQL) Inner VS Outer Join Having Vs Where Clause Database Objects Nested Queries in SQL Join operation Vs nested query Indexing in Databases | Set 1 SQL queries on clustered and non-clustered Indexes SQL Tutorial Transactions and concurrency control : Concurrency Control -Introduction Database Recovery Techniques ACID Properties in DBMS Log based recovery DBMS | Why recovery is needed? Transaction Isolation Levels in DBMS Concurrency Control | Types of Schedules DBMS | Types of Recoverability of Schedules and easiest way to test schedule Conflict Serializability Precedence Graph For Testing Conflict Serializability How to test if two schedules are View Equal or not ? Recoverability of Schedules Deadlock in DBMS Starvation in DBMS Concurrency Control Protocols | Lock Based Protocol Concurrency Control Protocol | Two Phase Locking (2-PL)-I Concurrency Control Protocol | Two Phase Locking (2-PL)-II Concurrency Control Protocol | Two Phase Locking (2-PL)-III Concurrency Control Protocol | Thomas Write Rule Concurrency Control Protocols | Timestamp Ordering Protocols Concurrency Control Protocol | Multiple Granularity Locking Concurrency Control Protocol | Graph Based Protocol Introduction to TimeStamp and Deadlock Prevention Schemes Implementation of Locking in DBMS DBMS | Challenges of database security File structures (sequential files, indexing, B and B+ trees) : Indexing in Databases | Set 1 File Organization – Set 1 File Organization – Set 2 (Hashing in DBMS) File Organization – Set 3 B-Tree | Set 1 (Introduction) B-Tree | Set 2 (Insert) B-Tree | Set 3 (Delete) Database File Indexing – B+ Tree (Introduction) RAID Data Warehousing Data Mining Data Replication CATEGORY ARCHIVES: DBMS Last Minute Notes – DBMS	ER‐model: ER and Relational Models Relational model (relational algebra, tuple calculus): ER and Relational Models Database design (integrity constraints, normal forms): Database Design(Normal Forms) Query languages (SQL) : SQL Transactions and concurrency control: Transactions and concurrency control File structures (sequential files, indexing, B and B+ trees): File structures (sequential files, indexing, B and B+ trees) Practice questions on B and B+ Trees Commonly asked DBMS interview questions | Set 1 Commonly asked DBMS interview questions | Set 2 Database Management Systems | Set 1 Database Management Systems | Set 2 Database Management Systems | Set 3 Database Management Systems | Set 4 Database Management Systems | Set 5 Database Management Systems | Set 6 Database Management Systems | Set 7 Database Management Systems | Set 8 Database Management Systems | Set 9 Database Management Systems | Set 10 Database Management Systems | Set 11	Databases : Video – NPTEL Lectures Notes – Lecture Slides Silberschatz, Korth and Sudarshan Notes – Lecture Slides Raghu Ramakrishnan and Johannes Gehrke Notes – Stanford DBMS course Lecture Slides Notes – Jeff Ullman's Lecture Slides Notes – Normal forms Notes – Canonical Cover Notes – Indexing Visual – B Tree Notes – B+ Tree Visual – B+ Tree
Section 7: Computer Networks Concept of layering: OSI and TCP/IP Protocol Stacks; Basics of packet, circuit and virtual circuit-switching; Data link layer: framing, error detection, Medium Access Control, Ethernet bridging; Routing protocols: shortest path, flooding, distance vector and link state routing; Fragmentation and IP addressing, IPv4, CIDR notation, Basics of IP support protocols (ARP, DHCP, ICMP), Network Address Translation (NAT); Transport layer: flow control and congestion control, UDP, TCP, sockets; Application layer protocols: DNS, SMTP, HTTP, FTP, Email.	Network Fundamental and Physical layer : Basics of Computer Networking Network goals Network Topologies Types of area networks – LAN, MAN and WAN MANET: Mobile Ad hoc Network Types of MANET Types of Transmission Media Transmission Modes in Computer Networks (Simplex, Half-Duplex and Full-Duplex) Redundant link problems Digital Subscriber Line (DSL) What is Scrambling? Difference between Unipolar, Polar and Bipolar Line Coding Schemes Manchester Encoding Analog to digital conversion Digital to Analog Conversion Analog to Analog Conversion (Modulation) Difference between Broadband and Baseband Transmission Let's experiment with Networking Layers of OSI Model TCP/IP Model Data Link layer : Multiple Access Protocols P2P(Peer To Peer) File Sharing Framing In Data Link Layer LAN Technologies | ETHERNET Ethernet Frame Format Token Ring frame format Bit Stuffing Difference between Byte stuffing and Bit stuffing Hamming Code Carrier sense multiple access (CSMA) Controlled Access Protocols Back-off Algorithm for CSMA/CD Collision Detection in CSMA/CD Efficiency of CSMA/CD Efficiency Of Token Ring Computer Networks | Error Detection Stop and Wait ARQ Sliding Window Protocol | Set 1 (Sender Side) Sliding Window Protocol | Set 2 (Receiver Side) Sliding Window Protocol | Set 3 (Selective Repeat) Sliding Window protocols Summary With Questions Program to remotely Power On a PC over the internet using the Wake-on-LAN protocol Program to calculate the Round Trip Time (RTT) Introduction of MAC Address Collision Avoidance in wireless networks Maximum data rate (channel capacity) for noiseless and noisy channels Types of switches Network layer : Internetworking Line Configuration in Computer Networks Difference between Unicast, Broadcast and Multicast Collision Domain and Broadcast Domain IP Addressing | Introduction and Classful Addressing Network Layer | Introduction and IPv4 Datagram Header Network Layer | Ipv4 Datagram Fragmentation and Delays Fragmentation at Network Layer Internet Protocol v6 | IPv6 Internet Protocol version 6 (IPv6) Header IP Addressing | Classless Addressing Supernetting 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 IPv4 classless Subnet equation Introduction to variable length subnet mask (VLSM) Network address translation (NAT) Types of Network address translation (NAT) Classification of Routing Algorithms – Set 1 Types of routing – Set 2 Classes of routing protocols – Set 3 Distance vector routing v/s Link state routing Fixed and Flooding Routing algorithms Routing v/s Routed Protocols Unicast Routing – Link State Routing Routing Protocols Set 1 (Distance Vector Routing) Route Poisoning and Count to infinity problem Onion Routing Router on a stick Internet Control Message Protocol (ICMP) | Computer Networks Hot Standby Router Protocol (HSRP) OSPF protocol fundamentals OSPF protocol States OSPF router roles and configuration Root Bridge Election in Spanning Tree Protocol Types of Spanning Tree Protocol (STP) EIGRP fundamentals Features of Enhanced Interior Gateway Routing Protocol (EIGRP) Routing Information Protocol (RIP) Routing Interface Protocol (RIP) V1 & V2 Link state advertisement (LSA) Administrative Distance (AD) and Autonomous System (AS) 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 Packet flow in the same network Packet flow in different network Difference between layer-2 and layer-3 switches What's difference between Ping and Traceroute? Computer Network | Servers What is Local Host? Transport layer : Transport Layer responsibilities Congestion Control Leaky Bucket Algorithm TCP | Services and Segment structure TCP Congestion Control TCP 3-Way Handshake Process TCP Connection Establishment TCP Connection Termination Error Control in TCP TCP Timers TCP flags TCP Server-Client implementation in C User Datagram Protocol (UDP) Differences between TCP and UDP Multiplexing and Demultiplexing in Transport Layer Application layer : Protocols in Application Layer DNS (Domain Name Server) | NetWorking Address Resolution in DNS DNS Spoofing or DNS Cache poisoning Why does DNS use UDP and not TCP? Dynamic Host Configuration Protocol (DHCP) DHCP Relay Agent How DHCP server dynamically assigns IP address to a host? Simple network management protocol (SNMP) Simple Mail Transfer Protocol (SMTP) File Transfer Protocol (FTP) HTTP Non-Persistent & Persistent Connection Multipurpose Internet mail extension (MIME) 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 Wifi protected setup (WPS) Wifi protected access (WPA) LiFi vs. WiFi Network Devices (Hub, Repeater, Bridge, Switch, Router and Gateways) Network security : Basic Network Attacks Types of Viruses Introduction to Firewall Zone-based firewall Firewall methodologies Deniel of Service and Prevention Cryptography | Introduction to Crypto-terminologies Denial of Service DDoS attack Types of DNS Attacks and Tactics for Security Types of Security attacks | Active and Passive attacks Birthday attack Digital Signatures and Certificates LZW (Lempel–Ziv–Welch) Compression technique RC4 Encryption Algorithm RC5 Encryption Algorithm SHA-512 Hash RSA Algorithm in Cryptography RSA Algorithm using Multiple Precision Arithmetic Library Weak RSA decryption with Chinese-remainder theorem Implementation of Diffie-Hellman Algorithm DNA Cryptography Port security Unicode Message Authentication Codes How message authentication code works? System security Hash Functions in System Security The CIA triad Image Steganography Access-lists (ACL) Data encryption standard (DES) Difference between AES and DES ciphers CATEGORY ARCHIVES: COMPUTER NETWORKS Last Minute Notes – Computer Networks	Network Fundamental and Physical layer : Computer Networks Data Link layer : Data Link Layer Network layer : Network Layer IP Addressing Transport layer : Transport Layer Application layer : HTTP Non-Persistent & Persistent Connection | Set 2 (Practice Question) Application Layer Network security : Network Security Commonly asked Computer Networks Interview Questions | Set 1 Computer Networks | Set 1 Computer Networks | Set 2 Computer Networks | Set 3 Computer Networks | Set 4 Computer Networks | Set 5 Computer Networks | Set 6 Computer Networks | Set 7 Computer Networks | Set 8 Computer Networks | Set 9 Computer Networks | Set 10 Computer Networks | Set 11 Computer Networks | Set 12	Computer Networks : Video – NPTEL Lectures Video – Lectures by Ravindrababu Ravula Notes – Lecture Notes IIT Kanpur Notes – Web Resources on Computer Networks by Tanenbaum Visual – Sliding Window Animation Notes – Sliding Window MIT Notes – IPv4 vs IPv6
Section 8: Computer Organization and Architecture Machine instructions and addressing modes ALU, data‐path and control unit Instruction pipelining, pipeline hazards Memory hierarchy: cache, main memory and secondary storage I/O interface (Interrupt and DMA mode)	Machine instructions and addressing modes : Von Neumann architecture Basic Computer Instructions Instruction Formats (Zero, One, Two and Three Address Instruction) Stack based CPU Organization General Register based CPU Organization Single Accumulator based CPU organization Problem Solving on Instruction Format Addressing Modes Machine Instructions Difference between CALL and JUMP instructions Simplified Instructional Computer (SIC) Hardware architecture (parallel computing) Flynn's taxonomy Generations of computer Amdahl's law and its proof ALU, data‐path and control unit : Control Unit and design Hardwired v/s Micro-programmed Control Unit Hardwired Vs Micro-programmed Control unit | Set 2 Horizontal micro-programmed Vs Vertical micro-programmed control unit Synchronous Data Transfer Instruction pipelining : Pipelining | Set 1 (Execution, Stages and Throughput) Pipelining | Set 2 (Dependencies and Data Hazard) Pipelining | Set 3 (Types and Stalling) Different Instruction Cycles Performance of Computer Micro-Operation RISC and CISC RISC and CISC | Set 2 Cache Memory : Memory Hierarchy Design and its Characteristics Cache Memory Cache Organization | Introduction Locality and Cache friendly code What's difference between CPU Cache and TLB? Read and Write operations in memory Memory Interleaving Introduction to memory and memory units 2D and 2.5D Memory organization Types of computer memory (RAM and ROM) Different Types of RAM RAM vs ROM I/O interface (Interrupt and DMA mode) : I/O Interface (Interrupt and DMA Mode) Input-Output Processor Kernel I/O Subsystem Memory mapped I/O and Isolated I/O BUS Arbitration Priority Interrupts | (S/W Polling and Daisy Chaining) Asynchronous input output synchronization Computer Ports Clusters In Computer Organisation Human – Computer interaction through the ages CATEGORY ARCHIVES: COMPUTER ORGANIZATION & ARCHITECTURE	Computer Organization and Architecture : Quiz on Microprocessors Computer Organization and Architecture	Computer Organization and Architecture : Video – NPTEL Lectures Book – Carl Hamacher Notes – Pipelining Notes – Cache Memory Notes – Cache Associativity
Section 9: Theory of Computation Regular expressions and finite automata Context-free grammars and push-down automata Regular and context-free languages, pumping lemma Turing machines and undecidability	Regular expression, langauges, grammar and finite automata : Introduction of Theory of Computation Finite Automata | Introduction Chomsky Hierarchy Regular Expressions, Regular Grammar and Regular Languages Pumping Lemma Arden's Theorem How to identify if a language is regular or not Designing Finite Automata from Regular Expression NFA with epsilon move to DFA Conversion Conversion from NFA to DFA Minimization of DFA Generating regular expression from finite automata Union & Intersection of Regular languages with CFL Designing Deterministic Finite Automata (Set 1) Designing Deterministic Finite Automata (Set 2) DFA of a string with at least two 0's and at least two 1's DFA machines accepting odd number of 0's or/and even number of 1's DFA for accepting the language L = {anbm | n+m=even} DFA for Strings not ending with "THE" Union process in DFA Concatenation process in DFA Star Height of Regular Expression and Regular Language Mealy and Moore Machines Difference between Mealy machine and Moore machine Context free langauges, grammar and push down automata : Pushdown Automata Pushdown Automata Acceptance by Final State Check if the language is Context Free or Not Construct Pushdown Automata for given languages Construct Pushdown automata for L = {0n1m2m3n | m,n ≥ 0} Construct Pushdown automata for L = {0n1m2(n+m) | m,n ≥ 0} Construct Pushdown Automata for all length palindrome NPDA for the language L ={wϵ{a,b}*| w contains equal no. of a's and b's} NPDA for accepting the language L = {an bn | n>=1} NPDA for accepting the language L = {an bm cn | m,n>=1} NPDA for accepting the language L = {an bn cm | m,n>=1} NPDA for accepting the language L = {am b(2m) | m>=1} NPDA for accepting the language L = {ambncpdq | m+n=p+q ; m,n,p,q>=1} Construct Pushdown automata for L = {a(2*m)c(4*n)dnbm | m,n ≥ 0} NPDA for accepting the language L = {ambnc(m+n) | m,n≥1} NPDA for accepting the language L = {amb(m+n)cn | m,n≥1} NPDA for accepting the language L = {a2mb3m | m≥1} NPDA for accepting the language L = {amb(2m+1) | m≥1} NPDA for L = {0i1j2k | i==j or j==k ; i , j , k >= 1} Closure Properties of Context Free Languages Ambiguity in CFG and CFL Simplifying Context Free Grammars Converting Context Free Grammar to Chomsky Normal Form Converting Context Free Grammar to Greibach Normal Form Relationship between grammar and language Context Sensitive langauges : Context-sensitive Grammar (CSG) and Language (CSL) Turing machines and undecidability : Recursive and Recursive Enumerable Languages Turing Machine Halting Problem Turing Machine for addition Turing machine for subtraction Turing Machine for subtraction | Set 2 Turing machine for multiplication Turing machine for copying data Construct a Turing Machine for language L = {0n1n2n | n≥1} Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}} Construct a Turing Machine for language L = {ww | w ∈ {0,1}} Construct Turing machine for L = {anbm a(n+m) | n,m≥1} Construct a Turing machine for L = {aibjck | i*j = k; i, j, k ≥ 1} Proof that Hamiltonian Path is NP-Complete Proof that vertex cover is NP complete Decidability Decidable and undecidable problems Undecidability and Reducibility Computable and non-computable problems CATEGORY ARCHIVES: THEORY OF COMPUTATION & AUTOMATA Last Minute Notes – Theory of Computation	Regular expression, langauges, grammar and finite automata : Regular languages and finite automata Practice problems on finite automata Practice problems on finite automata | Set 2 Context free langauges, grammar and push down automata : Context free languages and Push-down automata Context Sensitive langauges : . Turing machines and undecidability : Recursively enumerable sets and Turing machines Undecidability Automata Theory Automata Theory | Set 1 Automata Theory | Set 2 Automata Theory | Set 3 Automata Theory | Set 4 Automata Theory | Set 5 Automata Theory | Set 6	Theory of Computation : Video – NPTEL Lectures Video – Lectures by Ravindrababu Ravula Notes – NFA and DFA Notes – Non Regular language Notes – PDA Notes – Turing Machine Notes – Rice Theorem
Section 10: Compiler Design Lexical analysis, parsing, syntax-directed translation Runtime environments Intermediate code generation Local optimisation, Data flow analyses: constant propagation, liveness analysis, common subexpression elimination.	Introduction of Compiler : Introduction of Compiler design Phases of a Compiler Symbol Table in Compiler Static and Dynamic Scoping Generation of Programming Languages Error Handling in Compiler Design Error detection and Recovery in Compiler Linker Lexical analysis : Lexical Analysis C program to detect tokens in a C program Fast Lexical Analyzer Generator Parsing : Classification of Context Free Grammars Ambiguous Grammar Why FIRST and FOLLOW? FIRST Set in Syntax Analysis FOLLOW Set in Syntax Analysis Program to calculate First and Follow sets of given grammar Introduction to Syntax Analysis Parsing Set 1 Parsing Set 2 Parsing Set 3 Shift Reduce Parser in Compiler Classification of top down parsers Operator grammar and precedence parser Syntax directed transalation : Syntax Directed Translation S – attributed and L – attributed SDTs in Syntax directed translation Runtime environments : Runtime Environments Intermediate code generation : Intermediate Code Generation Three address code in Compiler Detection of a Loop in Three Address Code Code Optimization Introduction of Object Code Data flow analysis in Compiler CATEGORY ARCHIVES: COMPILER DESIGN Last Minute Notes – Compiler Design	Introduction of Compiler : MCQ on Memory allocation and compilation process Lexical analysis : Lexical analysis Parsing : Compiler Theory | Set 1 Compiler Theory | Set 2 Syntax directed transalation : Parsing and Syntax directed translation Runtime environments : . Intermediate code generation : Code Generation and Optimization	Compiler Design : Video – NPTEL Lectures Video – Lectures by Ravindrababu Ravula Book – Basics of Compiler Design Notes – Bivas Mitra IITgp Notes – LR Parsing Notes – Syntax Directed Translation Notes – Intermediate Code Generation
Section 11: Digital Logic Boolean algebra Combinational and sequential circuits. Minimization Number representations and computer arithmetic (fixed and floating point)	Introduction of Boolean Algebra and Logic Gates : Logic Gates Properties of Boolean algebra Minimization of Boolean Functions Representation of Boolean Functions Canonical and Standard Form Functional Completeness K-Map Implicants in K-Map PDNF and PCNF Variable entrant map (VEM) Consensus theorem Difference between combinational and sequential circuit Combinational Circuits : Half Adder Full Adder Half Subtractor Full Subtractor Half Adder and Half Subtractor using NAND NOR gates Encoders and Decoders Encoder Binary Decoder Combinational circuits using Decoder Multiplexers Carry Look-Ahead Adder Parallel Adder & Parallel Subtractor BCD Adder Magnitude Comparator BCD to 7 Segment Decoder Programmable Logic Array Programming Array Logic Read-Only Memory (ROM) Static Hazards Sequential Circuits : Introduction of Sequential Circuits Flip-flop types and their Conversion Synchronous Sequential Circuits Counters Ring Counter n-bit Johnson Counter Ripple Counter Design counter for given sequence Master Slave JK Flip Flop Asynchronous Sequential Circuits Shift Registers Design 101 sequence detector Amortized analysis for increment in counter 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? Booth's Algorithm Restoring Division Algorithm For Unsigned Integer Non-Restoring Division For Unsigned Integer CATEGORY ARCHIVES: DIGITAL ELECTRONICS & LOGIC DESIGN Last Minute Notes – Digital Electronics	Digital Logic : Digital Logic (101) Number representation	Digital Logic : Video – NPTEL Lectures Video – Lectures by Ravindrababu Ravula Notes – Number System-Swarthmore Notes – IEEE Standard 754 Floating Point Numbers

Last Updated on : 25th April, 2019

Other Useful Links :

1. Important Topics for GATE 2020 Computer Science

2. Last Minute Notes – GATE 2020

3. Top 5 Topics for Each Section of GATE CS Syllabus

4. GATE CS 2020 Syllabus

5. GATE CS 2020 Important Official Dates

6. Articles on Computer Science

7. Previous year papers GATE CS, solutions and explanations year-wise and topic-wise.

8. GATE CS 2018 Mock Tests

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above!

Mathematical Logic For Computer Science Gate Pdf

Source: https://www.geeksforgeeks.org/gate-cs-notes-gq/

Posted by: marcucciancessitere.blogspot.com

Share this post