What makes good CS problems?

csDirectives.md

Broad categories of CS directives.

(incomplete list)

Algorithms

• How do you reach from config to config using rules?
  • How many steps do you need?
  • Given config, rules and objective. How can you minimize/maximize objective?
  • Can you possibly reach from config to config`?
• Given setup, constraints and objective, can you achieve objective?
• Given problem, and an algorithm, does it work?
  • Does it work for a particular instance?
  • Find instances such that the algorithm does not work.
  • Given an incorrect/simplified version of algorithm, does it still work?
• Given problem, a resource and rules. How can you use resource the least to solve problem?
  • Given two algorithms, which uses resource the least?
• Given problem with an appealing greedy approach. Does the greedy approach indeed work?
  • Given a few greedy approaches, which one works?

Combinatorial Games

• Given a game on players, who has the winning strategy?
• Given game on players and strategy for player, does strategy work?
• Given game on players, find config such that player wins.

Graphs

• Can we reach from node to node following rules?
• What is the maximum/minimum number of nodes/edges of type can you touch while going from node to node?

csProblems.md

• What makes a Computer Science problem a Computer Science Problem?

  • Distinction is fuzzy.
    • Logic and Discrete Mathematics lie on the borderline.
  • A problem is usually Computer Science if it is one of the two things:
    • Shows the characteristic of requiring an algorithm
      • an algorithm is a method to solve a problem that can be scaled, i.e, done by a (fast) mechanical device without needing human opinion/intervention
    • Relates to the daily usage of computational devices
      • might directly reference hardware architecture, operating systems, databases, web sockets, compilers, etc
  • The following are the broad areas of Computer Science:
    • Theoretical
      • Algorithms
      • Computability Theory
        • Theory of Computation, Automata Theory, Halting Problem, Turing Machines
      • Complexity Theory
        • O Notation, P vs NP, etc
      • Information Theory
    • Not so theoretical
      • Programming Languages
      • Computational Methods
        • Numerical Analysis, Computational Physics
      • Artificial Intelligence
        • Machine Learning, Neural Networks
        • Computer Vision
      • Computer Based Mathematics
        • Computer Based Algebra Systems - Mathematica, Sage
        • Computer Based Theorem Proving - Coq, Isabelle
      • Cryptography
    • Practical
      • Software Engineering
      • Web Development
      • Databases
      • Operating Systems
      • Networks
      • Software Security
      • Microprocessor Architecture

• What is typically taught in an Indian Computer Science curricula?

  • Upto High School:
    • Recognizing the parts of a Computer
    • Some history of Computer Science
    • Some basic stuff about binary numbers
    • Basic ideas like what an algorithm is, what flowcharts are
    • Software Literacy
      • Using Browsers, Word Processors, Presentation Suites, Spreadsheets
    • Basics of Operating Systems
      • Linux is sometimes introduced
    • Some basic knowledge about the internet protocols
      • and some history of the internet
    • Some programming languages [See note 1]
      • LOGO
        • in a preliminary level to draw certain pictures (turtle graphics)
      • BASIC
        • Now being replaced by Java
      • C / C++ / Python
        • Only taught to high school seniors
    • Web Design
      • Introductory HTML
    • Databases
      • SQL is introduced only to high school seniors
    • Introduction to algorithms
      • Only to high school seniors
      • very preliminary
      • sorting, searching
      • linked lists, stacks, queues
  • What I learnt in my Computer Science program in Chennai Mathematical Institute?
    • Year I
      • Programming with Haskell
        • Functional Programming
      • Discrete Mathematics
      • Programming with Python
    • Year II
      • Theory of Computation
        • Automata Theory, Turing Machines, etc
      • Design and Analysis of Algorithms
    • Year III
      • Programming Language Concepts
        • Theory of what makes a good programming language, compilers, etc
    • Might take other electives later
  • What is taught in a typical Computer Science Engineering Program?
    • C or C++
    • Networks
    • Operating Systems
    • I am not sure about this.
      • I could possibly try finding out, though.

• What got Agnishom interested in Computer Science?

  • People around me
    • My father used to solve problems in science with numerical analysis techniques
    • bobbym showed me the power of computer algebra systems, much later
  • Will to build stuff
    • Appreciated the potential of being able to create interesting software, websites, etc
    • Appreciated the potential for generative art, generative music
    • This was more interesting than the potential for being able to solve mathematical problems
  • Computers seemed cool
    • Programming languages are fun to learn
    • Experimenting was easy. Did not require expensive resources. Mistakes do not have horrible consequences
    • Scope to learn complex systems that have a large impact on the real world
  • I like Discrete Mathematics
    • I learnt more about graph theory, design and analysis of Algorithms
    • (Also see people around me)
    • Algorithmic Puzzles like those on Project Euler, CodeChef, etc seemed interesting
      • Although I did not solve many of those

• What daily life problems does Algorithms solve?

  • Explicit usage of Algorithms
    • Google Maps, figuring out routes
    • Communication on the web, usage of Cryptography, error corrections, and many other techniques
    • Web searching
    • Spreadsheets in accounting and management
    • Recommendor Systems that pick out the best product for you
  • Usage of Algorithms without knowing it
    • A bunch of hard Computer Science problems, often NP Complete
      • Knapsack Problem
        • figure out the best way to pick out the food items in a canteen
        • which treasures should the thief take so that they fit in his bag
      • Various Kinds of Optimizing problems
        • Scheduling problems
        • Bin Packing Problems
      • Sudoku, Minesweeper
    • Data Structures
      • Organizing stuff for maximum productivity
    • Sorting and Searching
    • Shuffling Cards

• What resources can we use to get ideas for Computer Science solvables?

  • Books
    • Libraries
    • Magazines
    • Open Access Books
  • Online Tutorials
    • Text Tutorial
      • Brilliant Wikis, Geeks4Geeks
    • Video Tutorials
      • NPTEL Courses, Computerphile, Mifta Sintaha
    • Interactive Demonstrations
      • Visualgo
  • Programming Problem Repositories
    • Competitive Programming resources
      • Hackerrank, CodeChef, CodeForces
      • Sphere Online Judge
      • Computing Olympiad Problems
    • Interview Problems
      • Interviewbit, Careercup
    • Course Test Papers from Academia
    • Other resources
      • Brilliant, Project Euler
    • Forums or Q/A sites
      • Stack OverFlow, CS Stack Exchange, Programming Puzzles and Code Golf Stack Exchange
      • DailyProgrammers Subreddit
      • Quora
        • not very hopeful about Quora
    • Popular Culture related to CS
      • Memes/Jokes/Comics
      • xkcd, ProgrammingHumor, Silicon Valley

• Indirect Methods of Brainstorming for ideas

  • Searching the web for a specific CS term
    • when you already have something in mind
  • Brand a Discrete Mathematics or Logic Problem as CS
    • Especially graph theory
  • Exploit an existing concept from a CS point of view
    • like from a simulation point of view, for example

• Which areas of CS, in the above list have relatively low prerequisites?

  • The following have some potential (From highest to lowest potential, often with ties)
    • Algorithms
      • Highest potential
      • Encountered in Daily life
        • Can be presented as games
      • Little to no prerequisites.
        • Do not require any complicated looking math to describe (on the surface)
    • Programming Languages
      • Worthwhile exercise to understand how a simplified piece of instructions could work out to mean something with more structure.
      • Working out something step by step is not so trivial.
        • Loops, recursive functions, etc
    • Cryptography
      • Cryptography, broadly, is the art of writing confidential and authentic messages.
      • Certain cryptographic ideas involving protocols and security formulations could be easily explained.
    • Information Theory
      • Information Compression
      • Looks like algorithms, already
    • Theory of Computation
      • Some formulations of automata related problems, or Computability related problems
        • Consider the halting problem for example
    • Computational Methods
      • Numerical Analysis
        • Some ideas maybe presented in an elementary way.
    • Complexity Theory
      • Relatable to some extent in the context of elementary analysis of algorithms
  • These are areas in Discrete Mathematics and Logic that are often used in CS
    • Graph Theory
      • At the heart of several algorithms and data structures.
      • Requires no prerequisites to appreciate.
    • Combinatorial Game Theory
      • Because a strategy is really an algorithm.
    • Propositional logic / Logic Gates
      • Used in programming, circuitry, etc
    • Number Bases
      • Binary, Octal, Hexadecimal are often used in CS
  • I do not expect these areas to be very relatable
    • Computational Methods
      • Simulations, Computational Physics, Biology
    • Artificial Intelligence
      • Machine Learning, Pattern Recognition
    • Theorem Proving, Computer Algebra Systems
  • These are mostly engineering. These answers might change tomorrow. These problems cannot not have no prerequisites.
    • Software engineering, Databases, Operating Systems, Web Development, Networks, Software Security, Computer Architecture

• What programming language and style should we prefer?

  • Use pseudocode when you can.
    • Pseudocode is an unambiguous procedural description of algorithms which is readable, not too formal, and yet precise.
    • Pseudocode may have actual programming constructs including conditionals, loops, recursion
      • Better to avoid pointers, classes and more complicated stuff.
    • Natural language is often ambiguous. Natural language is not pseudocode.
  • When required (or when real code does not affect readablity), prefer python.
    • Python is readable
    • Focus on algorithms
      • and not low level details,
  • Prefer procedural style over functional.
    • Explicit is better than implicit.