Your browser does not support JavaScript

Bachelor Of Science In Computer Science, Bsc in Computer Science | India
Computer Science Programme

The undergraduate Computer Science (CS) major at Ashoka acknowledges the relevance of computing and information science to every academic discipline, and emphasizes exposure to interdisciplinary research that will drive innovation in the future. In addition to courses in traditional CS fields like systems, theory and AI, students will be able to leverage the multidisciplinary interests of the faculty to study newer fields like human-centered computing, social and information networks, digital humanities, data-driven journalism, and cyber law. They will not only develop a diverse set of skills to prepare for graduate school and for employment, but will also be encouraged to launch their own startups or venture into new types of careers using their interdisciplinary training.

 

Our curriculum takes into account the ACM curriculum guidelines for undergraduate degrees in computer science and exposes students to modern advancements and new sub-fields of computer science.

 

The main goals of the programme are:

  • Develop the core set of technical skills that will prepare students for employment or further studies

  • Gain a deeper understanding of the scientific and relevant mathematical underpinnings of computer science and learn to apply them practically

  • Identify and solve the most challenging computer science problems, and work towards developing new ideas and creating new knowledge in the field of computer science

  • Understand the social context in which students’ knowledge and work of computer science will be used, and engage in collaborative work with members of team outside the discipline

Apart from a major in CS, students can also opt for a minor in CS, or inter-disciplinary majors in CS and Entrepreneurship, and in CS and Mathematics. CS major students are strongly encouraged to enroll in the Ashoka Scholars Programme, which will confer postgraduate diplomas following a year of advanced study, research, and field work. This unique one-year programme combines a real-life, academically rigorous research project and internship taken alongside a set of electives, so that students can enter into successful academic and professional careers with ample experience in their fields.

 

The Department offers a doctoral program leading to a Ph.D. in Computer Science. Click Here for more information. 

Computer Science Major Requirements (3-years)

To receive a B.Sc. degree with a major in Computer Science at Ashoka University, students must accumulate 100 credit points at the end of three years. The course divisions and credit points requirement within three years for a major in Computer Science are as follows: 

 

  • Foundation and Critical Thinking courses (36 credits)
  • Co-Curricular courses (4 credits)
    • The foundation courses are drawn from multiple disciplines - history, economics, English etc with the aim to provide students with a strong foundation in the humanities and liberal arts. Visit https://ashoka.edu.in/page/undergraduate-academics-1# /section-52 for a complete description of foundation and co-curricular course requirements.
  • Computer Science Major courses (60 credits)
    • The course division for Computer Science Major courses is given below:
      • The student must complete 10 core CS courses for 40 credits. The 10 courses are listed below.
      • In addition to the 40 credits from core courses, students must take at least 20 credits of electives offered by the CS department.  

Computer Science Compulsory Courses:

  • Discrete Math
  • Probability and Statistics
  • Introduction to Computer Programming
  • Computer Organization and Systems
  • Advanced Programming
  • Operating Systems
  • Algorithm Design and Analysis
  • Computer Networks
  • Introduction to Machine Learning
  • Programming language Design and Implementation

Computer Science Elective Courses:

The list of computer science elective courses include, but not limited to,

  • Theory of Computation
  • Computer security and privacy
  • Introduction to Human Computer Interaction
  • Data Mining and Information Retrieval
  • Introduction to Data Bases
  • Unstructured Information Processing
  • Advanced Algorithms
  • Compilers
  • Networked and Social Systems
  • Information and Coding Theory
  • Computer Graphics
  • Software Engineering
  • Cyber Security
  • Distributed Systems
  • Practice-oriented courses (Mobile phone platforms, cloud computing, etc.)
Semester-wise Break-up of CS Course Structure

An example path through the CS major may look like this:

 

1st Semester

  • No CS courses

2nd Semester

  • Introduction to Computer Programming
  • Discrete Mathematics

3rd Semester

  • Probability and Statistics
  • Computer Organization and Systems
  • Advanced Programming

4th Semester

  • Algorithm Design and Analysis
  • Operating Systems
  • CS Elective

5th Semester

  • Computer Networks
  • Introduction to Machine Learning
  • Programming Language Design and Implementation
  • CS Elective

6th Semester

  • CS Elective
  • CS Elective
  • CS Elective
Course Descriptions

Discrete Mathematics: This course introduces and develops proficiency in use of some of the key mathematical tools and techniques that students require for careful analysis in computer science. The course emphasizes creative problem solving, rigorous analysis and reading and writing formal proofs. Topics include discrete probability, advance counting techniques like recurrence relations and generating functions, modular arithmetic and finite fields with applications to coding theory and cryptography, matching, cuts, flows and connectivity in graphs. & Students are highly encouraged to take the Introduction to Mathematical Thinking foundation course before taking this course. If you have not previously taken this FC, or if you have not taken mathematics in the Class 11/12/PUC level, consult your academic advisor before enrolling. Although a CTS course, this course is required for all CS majors. There is a higher enrolment cap in this course compared to most other CTS classes.
 

Probability and Statistics: Discrete probability distribution. Continuous probability distribution. Random Variable. Expectation, variance, covariance, and moment generating functions. Probabilistic Inequalities. Weak variant of Law of Large Numbers. Special Random Variables: Uniform, Bernoulli, Binomial, Poisson, Hypergeometric, Normal, Gamma, Chi-square, t-distribution. Distributions as approximation of Normal. Simulation: generating random variables (discrete and continuous). Central Limit Theorem. Descriptive Statistics. Distribution of Sampling Statistics. Parameter Estimation. Hypothesis Testing. Regression & Students are highly encouraged to take the Introduction to Mathematical Thinking foundation course before taking this course. If you have not previously taken this FC, or if you have not taken mathematics in the Class 11/12/PUC level, consult your academic advisor before enrolling.
 

Introduction to Computer Programming: This course is an introduction to computing, with emphasis on solving problems by writing programs. The focus will be on problem solving, and not on the syntax of any particular programming language. The course will introduce program structures (loops, conditionals, functions) and several data structures for efficient storage of information. The course may be based on different programming languages in different years, but will typically cover one or more out of the following languages: C, Python, Java and ML. It will include multiple programming assignments and give students the confidence to write and debug programs.

There is no pre-requisite for this course. No previous background in programming from high school is needed. This course is also open to students not aiming for a CS major. Therefore non-CS students who would like some knowledge about programming are encouraged to take this course.
 

Computer Organization and Systems: Basic machine organization, including processors, instruction sets, assembly-language programming, pipelining, memory, and input/output architecture. Basics of the memory hierarchy, including virtual memory and caches, and how these are implemented in hardware and software. Core concepts of operating systems, including processes, threads, synchronization, virtual memory policies, and file management.

Pre-requisite: Introduction to Computer Programming
 

Advanced Programming: Skills and knowledge required for professional programming and development. Problem and system decomposition and integration. Co-operative programming. Source code and version control system. Issue tracking system. Build automation. Automated testing and test driven development. Source tree and code organization. Code readability. Defensive coding and error handling. Performance optimization and tuning. Integrated Development Environments (IDEs), Application Programming Interfaces (APIs) and Frameworks. Scripting. Programming of large scale systems. Systematic debugging. Fundamentals of writing clean code.

Pre-requisite: Introduction to Computer Programming
 

Operating Systems: This course explores the design and implementation of operating systems. Topics include process synchronization and inter-process communication, processor scheduling, memory management, virtual memory, interrupt handling, device management, I/O, and file systems. It involves the hands-on study of the Linux operating system design and kernel internals, including work with Android devices and gives students experience with commercial virtualization tools and open source software.

Pre-requisite: Introduction to Computer Programming
 

Algorithm Design and Analysis: How do you optimally encode a text file? How do you find shortest paths in a map? How do you design a communication network? How do you route data in a network? What are the limits of efficient computation? This course gives a comprehensive introduction to design and analysis of algorithms, and answers along the way, these and many other interesting computational questions. You will learn about problem-solving; advanced data structures such as universal hashing and red-black trees; advanced design and analysis techniques such as dynamic programming and amortized analysis; graph algorithms such as minimum spanning trees and network flows; NP-completeness theory; and approximation algorithms.

Pre-requisite: Introduction to Computer Programming, Discrete Mathematics, Probability and Statistics
 

Computer Networks: Data communication fundamentals: Channel characteristics, transmission media, modulation.

Direct Link Networks: Encoding, synchronization, framing, error detection, reliable transmission, multiple access media, local area networks (LANs), MAC protocols, Wireless networks.

LAN Extension: Switches, packet switching.

Internetworking: Routers, the Internet Protocol, routing problem.

End-to-end Protocols (transport layer protocols): UDP, TCP. Application-level protocols: HTTP, FTP, SMTP, DNS, Socket Programming.

Pre-requisite: Introduction to Computer Programming, Probability and Statistics, Discrete Mathematics.

 

Programming language Design and Implementation: What makes a programming language like “Python” or “Java?” This course will look past superficial properties like syntax and at the core properties of programming languages. It will explore a variety of topics in programming language construction and design: syntax and semantics, mechanisms for parameter passing, typing, scoping, and control structures. It will also consider implementation aspects in language runtimes such as just-in-time compilation and garbage collection. Students will be exposed to multiple programming paradigms, including functional languages like Scheme and ML, object-oriented languages like Java, C++ and Javascript, and logic programming languages like Prolog and Datalog.

Pre-requisite: Introduction to Computer Programming, Advanced Programming
 

Theory of Computation: This course is an introduction to models of computation, computability, and complexity. We will ask questions like: How do we define the abstract notion of “computation” or a “computer”? What problems can be computed? What problems can be computed efficiently? Can we prove that some problems can never be computed, no matter how fast our computers become? The course is highly mathematical and abstract; in particular, there will be minimal programming assignments (if any) and homework problems will frequently involve proving or disproving various assertions. Sample topics: automata and the languages they define, context-free grammars and the languages they define, Turing machines, basic complexity theory (such as P vs. NP).

Pre-requisite: Introduction to Computer Programming, Advanced Programming, Algorithm Design and Analysis, Discrete Mathematics.
 

Computer security and privacy: This course covers a variety of topics in computer security: overview of cryptography, common vulnerabilities, web security, network security, Malware, denial of service, mobile platform security, coding secure systems, security testing and tools, security and human factors; privacy: history, tracking, and survey of legal issues, programming projects for analysis/test of software for vulnerabilities.

Pre-requisite: Introduction to Computer Programming, Computer Networks, Discrete Mathematics, Probability and Statistics
 

Introduction to Human Computer Interaction: This is an introductory course in human-computer interaction. The course introduces students to basic HCI techniques like rapid prototyping, contextual inquiry, formulating and conducting user studies, idea logs, visual design, experiments with human subjects and statistical analysis of these experiments using the R programming language. It covers topics like input/output technologies, web and mobile interfaces, crowdsourcing, visualization tools and techniques, life-logging and technologies for development (ICTD). While being grounded in computer systems work, students will develop an appreciation for the human in the loop, and make connections to other disciplines in the humanities (sociology, psychology, design, ethnography). This course prepares students for research in HCI and imparts essential skills needed in the creation of consumer and enterprise products. This course is also open to students not aiming for a CS major. Students will work in teams on a semester-long project, but not everyone is expected to be a programmer.
 

Information Retrieval: Basic and advanced techniques and concepts for text-based information retrieval systems. Goals and history of information retrieval. Boolean retrieval. TF-IDF (term frequency/inverse document frequency) weighting and cosine similarity. Simple tokenizing, stop-word removal, and stemming. Term vocabulary and postings lists. Dictionaries and tolerant retrieval. Index construction. Scoring, term weighting and the vector space model. Evaluation in information retrieval. Probabilistic information retrieval. Text classification and Naive Bayes. Vector space classification. Flat clustering. Web search basics and Link analysis.
 

Software Engineering: Fundamentals of software engineering and topics covering all aspects of software development from system specification to the maintenance after deployment. The course will cover theory, methods and tools for professional software development through lectures and a semester-long team-based project. List of topics are: requirements engineering, system analysis, low-level and high-level design and architecture, coding, integration, design and code reviews, documentation, testing and quality assurance, maintenance, project management and configuration management.
 

Introduction to Databases: Fundamentals and key concepts of databases. Database design, implementation and applications. The focus will be on relational database concepts but the course will cover recent industry developments in database systems such as NoSQL databases during the advanced stages of the course. List of topics are: basic concepts of the relational model and its mathematical foundation, SQL language to define, query and manipulate a relational database, database design and conceptual modelling using entity-relationship model and diagrams, indexed organization, normalization, transaction processing and management.
 

Computer Science Minor Requirements

In order to get a Minor in Computer Science, students are required to take

  • Introduction to Computer Programming, and

  • five more CS courses. Of these five, at least 3 of them must be from CS core courses list.

Interdisciplinary Majors

In order to major in an interdisciplinary degree, students must accumulate 116 credit points at the end of three years - i.e., 16 credit points more than what is required for a pure Major.

Computer Science department offers two interdisciplinary majors - Computer Science and Mathematics; Computer Science and Entrepreneurship. The course divisions and credit points requirement within three years for these two Interdisciplinary Major are as follows:

  • Foundation and Critical Thinking courses (36 credits)
  • Interdisciplinary Major courses (76 credits)
  • Co-Curricular courses (4 credits)

Computer Science and Mathematics

The course division between Computer Science and Mathematics department for this interdisciplinary major is given below. The requirements below, 1 through 5, are all mandatory.

  • A minimum of 76 credit points of Interdisciplinary Major courses.
  • A minimum of 36 credit points of courses offered by Computer Science.
  • A minimum of 36 credit points of courses offered by Mathematics.
  • Must complete 7 core courses, offered by Computer Science, for 28 credit points.The CS core course list is given below.
  • Must complete 7 core courses, offered by Mathematics, for 28 credit points. The Math core course list is given below.

 

 

Computer Science

Mathematics

 

 

 

Compulsory Courses

Introduction to Computer Programing

Linear Algebra

Computer Organization and Systems

Algebra I

Algorithm Design and Analysis

Probability

Computer Networks

Real Analysis

Introduction to Machine Learning  Calculus I

Computer Security and Privacy

Linear Programming

Theory of Computation

Statistics

 

 

Computer Science and Entrepreneurship

Under this interdisciplinary major, students, in addition to 4 courses (16 credits) in Entrepreneurship programme, must complete all computer science pure major requirements.

Advanced Major in Computer Science

To graduate with a Postgraduate Diploma in Advaced Studies and Research (DipASR) in Computer Science at Ashoka University, students must accumulate 32 credit points at the end of one year. The course divisions and credit points requirement DipASR in Computer Science are as follows.

  • A minimum of 32 credit points is required.
  • A minimum of 16 credits from computer science department is required.
  • Mandatory completion of CS498: Capstone Project for 4 credits.
Project Description

S498: Capstone Project [4 Credits]: The student(s) are expected to work on implementation based projects. At the end there would be a project presentation of the work done and possible future work on the same problem if continued for Capstone Thesis.

 

CS499: Capstone Thesis [8 Credits]: Capstone Thesis is not mandatory. Enrollment to Capstone Thesis is done through a screening that takes into account one’s performance in CS498. The student(s) who work on a capstone thesis are expected to work towards the goalsand milestones set in capstone project CS498. At the end there would be a thesis presentation of the work done and possible future work on the same problem. A dissertation outlining the entire problem, including a survey of literature and the various results obtained along with their solutions is expected to be produced. The research work done in the thesis may requirecoding and implementation but it is the research which is the primary focus. The purpose of a project/thesis is to allow a student to identify a topic of their choice and interest in their 4th year and do an in-depth investigation and substantial work on the chosen topic under the supervision of an adviser. A project mentor could be from outside Ashoka. However, the project mentor from outside Ashoka should be a co-guide and a secondary adviser but not a primary adviser. In order to promote outstanding research and application, a project work making a substantial contribution will be considered for best project award. A student is required to submit two copies of the thesis.

Faculty
Visiting Faculty
  •  Prof. Dheeraj Sanghi, IIT Kanpur, Spring 2015
  •  Prof.Naveen Garg, IIT Delhi, Monsoon 2015
  •  Prof. Sanjiva Prasad, IIT Delhi, Monsoon 2015
  •  Dr. Sriram Vajapeyam, Spring 2016
  •  Dr. Raghavendra Singh, IBM Research India, Monsoon 2016
  •  Dr. Ravi Kothari, IBM Research India, Monsoon 2016 and Spring 2017
  •  Prof.Ragesh Jaiswal, IIT Delhi, Monsoon 2016
  •  Prof.Ansuman Banerjee, ISI Kolkata Spring 2017
  •  Prof.Subhamoy Maitra, ISI Kolkata, Spring 2017
  •  Prof.Brian Barsky, UC Berkeley, Spring 2017
  •  Dr. Vivek Seshadri, Microsoft Research India, Monsoon 2017

 

Advisors
Research

The computer science program encourages students to apply their technical knowledge and skills in diverse settings. The emphasis is on novel research themes that cut across several disciplines, and faculty members and students are actively engaged in research in the areas of human-computer interaction, cognitive psychology and political science.

 

Cognitive Experiments on Life-Logs (CELL)

CELL is an ongoing project at Ashoka University that seeks to leverage the power of email life-logging to understand cognitive processes related to memory, through Memories USing Email (MUSE), a program developed at Stanford University. Researchers at Ashoka have developed a novel approach to test the memory of personally familiar proper names among adults, through computerized text-based analysis of their emails. MUSE can be applied as a web-based measure to study cognition and functioning using more personalized information and thus represents the emergence of a new approach in cognitive neuroscience using life-log data. Click here to know more about CELL.

 

Indian Political Data Analysis 

The Trivedi Centre for Political Data in association with the Computer Science Programme at Ashoka aims to promote data-driven research, policy work and journalism by providing open access to scientifically collected and treated political data and by offering data services to non-profit organizations. This collaboration aims at putting together empirically sound data and information on matters of public interest, and can become a major tool for anyone interested in public debate in India. Click here to know more.

 

ePADD

ePADD is a program for libraries, archives and museums to process the email archives of eminent individuals, and make them available for historical research. It employs natural-language processing and visualization techniques to make it easy to work with long-term email archives. ePADD is a joint project with Stanford University. Click here to know more.

Maths-CS Colloquium, Spring 2017

Date: 4th April, 2017

Speaker: Sharan Gopal, BITS Hyderabad

Title: Topological Dynamics and Significance of Periodic Points

Abstract:

This talk is broadly in the area of Topological Dynamics, a well studied branch of Mathematics. We will start with a trivial example, thereby introducing the notion of a “dynamical system”. Then, some technical terms in the theory of dynamical systems are discussed followed by few examples. We will then consider the problem of characterizing the sets of periodic points of various families of dynamical systems. We will start with some results that are available in the literature on this problem and then discuss in detail, the characterization of periodic points of solenoidal automorphisms, a recently published result in collaboration with C.R.E. Raja (ISI, Bangalore). Finally, we conclude with a question on solenoids, which is actually an extension of the results, just mentioned.

 

Date: 28th March, 2017

Speaker: Tulsi Srinivasan, Ashoka

Title: The LS-category

Abstract:

The Lusternik-Schnirelmann category (LS-category) is a topological invariant with a rich history. We will look at how it was used in the 1930s to give a proof of the Borsuk-Ulam Theorem, an important result in topology, as well a modern application of it to topological robotics. I will also talk about how the theory of the LS-category can be extended to fractal spaces, and some possible applications of this to hyperbolic groups.

 

Date: 27th March, 2017

Speaker: Shobha Madan, IISER Mohali

Title: The Vandermonde Matrix and Uncertainty

Abstract: (None provided)

 

Date: 21st March, 2017

Speaker: Nutan Limaye, IIT Bombay (together with the Women in Computing Society)

Title: Data streams: how large a notebook do you need for Subset Sum?

Abstract:

In this talk we will discuss the classical Subset Sum problem, which is as follows: given a list of n numbers and a target B, check whether there is a subset of these numbers that adds to exactly B. The problem in its full generality is well-studied and is known to be NP-complete. We will consider different versions of the problem such as the Unary Subset Sum (USS) problem and Approximate USS problem.

 

We will consider these problems in the model of data streams, wherein the list of elements is presented one element at a time. The goal is to check whether there is a subset of numbers in the list that adds to the target sum (or to a number close enough to the target sum) by using as less memory as possible. We will give tight upper and lower bounds for the problem. This talk is based on the following two papers.

 

The Complexity of Unary Subset Sum.

Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah, appeared in Computing and Combinatorics - 18th Annual   International Conference, COCOON 2012.

 

Space-Efficient Approximations for Subset Sum.

Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah, appeared in ACM Transactions on     Computation Theory, Volume 8, 2016.

 

Date: 20th March, 2017

Speaker: Jean-Marc Deshouillers, Ashoka

Title: Automatic sequences and Sarnak’s conjecture 2

Abstract:

The distribution of prime number seems to have a high degree of randomness. Following Chowla, Sarnak introduced a conjecture according to which ‘primes are orthogonal to any sequence produced by a dynamical system of low complexity’. Sequences produced by a deterministic finite automaton have a low complexity and are good candidates for checking Sarnak’s conjecture. M\¨{u}llner proved that such sequences satisfy Sarnak’s conjecture. The special case when the automaton is synchronizing had been previously proved by him, Deshouillers and Drmota. In this talk in two parts, we shall present Sarnak’s conjecture and automatic sequences and outline the proof of M\¨{u}llner’s Theorem.

 

Date: 18th March, 2017

Speaker: Prathamesh Turaga, IMSc Chennai

Title: Mechanising mathematics

Abstract:

Mechanisation of Mathematics refers to the use of computers to generate or check mathematical proofs. An interactive theorem prover is a software tool which partly automates and checks such proofs by human-machine collaboration. The potential impact of recent developments in interactive theorem proving on the practice of everyday mathematics range from their use in verification of controversial mathematical proofs, such as classification of finite simple groups and Kepler conjecture, to a renewed interest in logical foundations of mathematics (Homotopy Type Theory by Voevodsky et al). This departs from the conventional use of computers for the purpose of calculation or simulation using computer algebra systems like Mathematica, Matlab and R.

 

In this talk, I intend to present a brief survey of the history and the current developments in interactive theorem proving and address questions about the necessity and importance of such an endeavor. I intend to present a working demonstration of an interactive theorem prover called Isabelle, and briefly discuss my work on formalization of knot theory in an interactive theorem prover called Isabelle.

 

Familiarity with interactive theorem proving or knot theory shall not be assumed.

 

Date: 11th March, 2017

Speaker: Krishanu Maulik, ISI Kolkata

Title: Urn models

Abstract:

Urn models were introduced by Eggenberger and Polya in 1923. Since then the model has been studied intensively and found applications in modelling social behaviour, gas laws, population dynamics, database management, reinforced learning, analysis of algorithms, clinical trial and so on. We shall consider several interesting examples and properties of urn models along with some applications. We shall also consider some results giving the asymptotic behaviour of the model.

 

Date: 8th March, 2017

Speaker: Sandeep Shukla, IIT Kanpur

Title: How Safe are our Critical Infrastructures from Cyber Attacks?

Abstract:

Last year Ukraine suffered a prolonged blackout of its power system induced by cyber attacks. The same repeated last month as well. Turkey's banking network was under attack last year slowing down all banking transactions for two consecutive days leading to major economic loss. Kaspersky's 2016 predictions on cyber thread situation in January 2016 included warning for interference through cyber attacks into their presidential election process and all signs indicate that it happened. Kaspersky's 2017 prediction has ominous warnings for possible compromise of 2017 European electoral processes. An analysis of 2012 July blackout shows that even though it was not a cyber attack induced massive blackout but one can conceive of a similar situation by cyber attack through systematic encroachment of advanced persistent threats into various PMUs, digital relays, and other IEDs.

 

In this talk we will talk briefly about the threat landscape for our national critical infrastructure, and outline some directions that we should consider following to enhance the cyber protection and resilience of our critical infrastructure.

 

Date: 7th March, 2017

Speaker: M. Krishna, Ashoka

Title: Counting the number of  tridiagonal Hermitian matrices with same eigenvalues

Abstract:

Inverse spectral theory is a deep study of recovering a potential configuration from

the spectrum of a Schrodinger operator in Quantum Mechanics.  This problem will be

presented in a simple form of recovering a tridiagonal Hermitian matrix from its eigenvalues

and counting  them. The background needed is linear algebra, complex analysis and calculus.

 

Date: 28th February, 2017

Speaker: Anima Nagar, IIT Delhi

Title: Flip-flops observed in dynamical systems

Abstract:

Dynamical systems are essentially the study of asymptotic behaviour of orbits of all points in the phase space. But there are flip-flops observed - some orbits are finite but some are dense. Can there be a connection between this behaviour? We try to discuss this unanswered question.

 

Date: 21st February, 2017

Speaker: Debyajoti Bera, IIIT Delhi

Title: Get large graphs by their ears

Abstract:

Large graphs are now commonly getting generated from various sources necessitating a second look at existing graph processing algorithms which do not often scale nicely with increasing size of graphs. With the rise in platforms and techniques which support parallel processing (multi-core architecture, GP-GPU, Map-Reduce, etc.), a natural way to parallelize graph algorithms is to decompose a graph into smaller subgraphs, process them individually, and then combine those results. This is a natural trend followed in recent graph algorithms.

 

We apply this technique for finding betweenness centrality of large, preferably sparse, graphs. The primary tool we use for graph decomposition is ear-decomposition of biconnected components which we use to also effectively reduce the size of graph instances. We devise a few algorithmic and engineering optimizations as well. We discuss a few experimental comparison of our approach with a few recent GPU-based approaches for betweenness-centrality and found noticeable improvements for several real-world datasets and randomly generated graphs.

 

This is a joint work Kishore Kothapalli (IIIT-H) and his students Charudatt Pachorkar, Meher Chaitanya which appeared in HiPC 2016.

 

Date: 14th February, 2017

Speaker: Thilo Weinert, BGU Israel

Title: The Ramsey Theory of Ordinals

Abstract:

Ramsey Theory is a branch of mathematics which is oftentimes summed up by the slogan “complete disorder is impossible”. A classical example is the Theorem on Friends and Strangers stating that in every party with six guests there is a group of three people who are either all mutually acquainted or all mutually unacquainted. More abstractly this amounts to asking whether for an edge-colouring of a complete graph there is a homogeneous set of vertices (a set of vertices such that all edges between them get the same colour) of a certain size. This problem can be considered both in the finite and infinite. In the infinite, considering structural aspects as simple as order can make a difference. We are going to consider these questions for the simplest cases of infinite linearly ordered sets—countable ordinals.

 

Date: 10th February, 2017

Speaker: Kannan Srinathan, IIIT Hyderabad

Title: The four pillars of computational thinking

Abstract:

In this talk, we illustrate that computational issues can be typically tackled in four different ways, namely, (a) starting at the right point (like Shannon's digitalization, Aryabatta's zero, Turing's universal machine etc.), (b) understanding and re-cycling the run-time uncertainties (like randomization, robustness, quantum uncertainty etc.), (c) flowing with finesse (like generality, feasibility, optimality etc.) and (d) stopping well-in-advance (like super-resolution, proactiviation, pseudorandomness etc.). For each of the four ways, we discuss famous examples that used them to solve important problems in the past and also speculate about what problems of the future could be similarly addressed

 

Date: 7th February, 2017

Speaker: Jean-Marc Deshouillers, Ashoka

Title: Automatic sequences and Sarnak’s conjecture 1

Abstract:

The distribution of prime number seems to have a high degree of randomness. Following Chowla, Sarnak introduced a conjecture according to which ‘primes are orthogonal to any sequence produced by a dynamical system of low complexity’. Sequences produced by a deterministic finite automaton have a low complexity and are good candidates for checking Sarnak’s conjecture. M\¨{u}llner proved that such sequences satisfy Sarnak’s conjecture. The special case when the automaton is synchronizing had been previously proved by him, Deshouillers and Drmota. In this talk in two parts, we shall present Sarnak’s conjecture and automatic sequences and outline the proof of M\¨{u}llner’s Theorem.

 

Date: 31st January, 2017

Speaker: Shanta Laishram, ISI Delhi

Title: On Ramanujan Primes

Abstract:

One of the well known results in prime number Theory is Bertrand's Postulate which states that there is at least one prime between n and 2n for any natural number n>1. Ramanujan gave a beautiful generalization of this result by showing that the interval $(x/2, x]$ contains a lot of prime number for any real $x\geq 2$and hence at least one prime proving Bertrand's Postulate.

 

The n-th Ramanujan prime is defined as the least positive integer $R_n$ such that for all $x \geq R_n$ , the interval ( x/2 , x] contains at least n primes. First few Ramanujan primes are

\begin{align*}

R_1=2, R_2=11, R_3=17, R_4=29, R_5=41, R_6=47, R_7=59, R_8=67, R_9=71, R_{10}=97.

\end{align*}

We will look  at some interesting facts surrounding these primes. Specifically we will look at bounds on these primes. One of the first upper bounds for $R_n$ was given by Laishram, who showed that $R_n < p_{3n}$ for all $n$, where $p_i$ is the i-th prime proving a conjecture of Sondow. We present various improvements on this upper bound and answer a conjecture of Sondow, Nicholson, Noe. This is a joint work with A. Srinivasan.  


 

Date: 24th January, 2017

Speaker: Indranil Dutta, EFLU

Title: Coarticulatory propensity in vowel harmony languages: Evidence from automatic

classification

Abstract:

Speech, an analog phenomenon, has traditionally been modeled through discrete mechanisms and processes. These methods have given way to dynamic approaches to speech processing that rely on modeling the non-linear and non-contiguous co-production or coarticulation of speech gestures. Acoustic variation due to vowel-to-vowel coarticulation, once phonologized, has been shown to be a conditioning factor for development of vowel harmony patterns (Przezdziecki 2000, Ohala 1994). The resultant reduction in phonetic distinctiveness between vowels, however, is known to be compensated perceptually (Beddor et al. 2002). In this presentation, we report on results from artificial neural network (ANN) and support vector machine (SVM) models trained to predict the identity of the vowels in V1CV2 sequences. We find that our models predict the identity of V1 consistently better than V2 in Telugu non-harmonic V1CV2 sequences, and V2 consistently better than the V1 in Bengali non-harmonic and harmonic sequences. We believe this directionality reflects the relative extent of coarticulatory effects in the anticipatory and carryover directions. We show that while vowel harmony patterns advanced from the anticipatory direction leading to neutralization of vowel contrasts between /iCu/->[uCu] sequences in Telugu, and Advance Tongue Root (ATR) harmony in Bengali, the extent of carryover coarticulation is still greater in non-harmonic contexts for Telugu even though it remains greater in the anticipatory direction in Bengali. Coarticulatory propensity and directionality, therefore, crucially interact with parametric notions of contrast in languages that exhibit vowel harmony.

FAQs

1. How will CS at Ashoka be different from that at other Indian universities?

Traditionally, in India, CS has been a part of engineering schools which tend to emphasize general engineering knowledge such as mechanics, electrical systems, manufacturing processes, chemistry, etc.  At Ashoka, our general curriculum has a much broader emphasis as reflected in the foundation courses and writing requirements.

 

2. Why is this important?

CS today is no longer just a technical/engineering discipline.  Think of the role computer scientists play in technologies that affect society at large, such as social networks, mobile phones, e-commerce, e-governance, cyber-warfare, and various other IT products and services.  We believe that the education needed to thrive and lead in these areas goes well beyond what is covered by engineering alone. Examples like Facebook, Twitter and Wikipedia show us the power of combining technology with insight into the human world.  We’d like to enable our students to have similarly impactful ideas.

 

3. What’s new in Ashoka CS?

In the core CS curriculum, we have included modern areas like human-computer interaction and networked systems, which gel well with our mission as stated in #1. These areas have a lot of scope for inter-disciplinary work and research, leveraging Ashoka‘s access to expert faculty in a wide range of areas.

 

4. Are we giving up on rigor in CS, because we build upon a broad-based curriculum?

Absolutely not. The curriculum for the CS major is similar to what is being taught in, say, the IITs; taken together with CS electives, we fully expect that our students will be ready to take on graduate studies in any of the top universities in the world, if they would like to.

 

5. Does it matter whether my degree is called a B.Sc, B.E. or B.Tech?

It’s a matter of nomenclature and doesn’t make any real difference for most purposes. The number of years of education is more important than what the degree is called. We highly recommend that CS majors stay at Ashoka for the +1 year of the Scholars program, in order to get the full benefit of a 4 year CS education.

 

6. How do I choose a major or minor programme at Ashoka?

At Ashoka University, students choose their own majors, after sampling various courses in a variety of disciplines. Instead of being slotted into majors, students discover where their true passions lie, and are encouraged to follow them. It is not uncommon for students to pursue a minor in, say, history or literature or performing arts, in addition to a major in CS. We also offer the ability to do dual-majors in CS and entrepreneurship or CS and mathematics.